Algorithm Day64 - Search Insert Position

Posted on Edited on In , Views:

🧩 Problem Description

Given a sorted array of distinct integers and a target value, return the index if the target is found.
If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

💬 Examples

Example 1

1
2
Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2

1
2
Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3

1
2
Input: nums = [1,3,5,6], target = 7
Output: 4

💡 Intuition

The array is sorted, so binary search is the best choice.

  • Maintain two pointers left and right.
  • While left <= right, check the middle value.
  • If nums[mid] == target, return mid.
  • If nums[mid] < target, move left = mid + 1.
  • Else move right = mid - 1.

Finally, left will be the correct insert position.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left; // insert position
    }
}

⏱ Complexity Analysis

  • Time: O(log n) due to binary search.
  • Space: O(1) since no extra memory is used.

✍️ Summary

  • Use binary search instead of linear scan.
  • If target not found, the correct insert position is left.

Related problems

  • lc-34 — Find First and Last Position of Element in Sorted Array
  • lc-704 — Binary Search