Search Insert Position

Problem Link

search-insert-position

Problem Statement

You are 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 inserted in order.

The solution must have a runtime complexity of O(log n).

Examples:

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

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

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

Constraints:

• 1 <= nums.length <= 10^4

• -10^4 <= nums[i] <= 10^4

• nums contains distinct values sorted in ascending order

• -10^4 <= target <= 10^4

Intuition

The array is sorted, and we are required to find either the exact index of the target or the position where it can be inserted while maintaining the order. Since this must be done in O(log n) time, Binary Search is the appropriate approach.

The key is that if the target is not found, the left pointer (start) will always end up at the correct insertion position after the loop ends.

Approach

1. Initialize two pointers:
   start = 0, end = nums.length - 1

2. While start <= end:
   a. Compute mid = start + (end - start) / 2
   b. Compare nums[mid] with target:

   • If nums[mid] == target: return mid

   • If nums[mid] > target: move left → end = mid - 1

   • If nums[mid] < target: move right → start = mid + 1

3. If the loop ends without returning, the correct position to insert the target is at index start. Return start.

Code in Java

class Solution {
    public int searchInsert(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return start;
    }
}

Time and Space Complexity

• Time Complexity: O(log n)
  Each iteration halves the search space.

• Space Complexity: O(1)
  Only a constant amount of extra space is used.

Dry Run

Input:

nums = [1, 3, 5, 6], target = 2

Steps:

• start = 0, end = 3

• mid = (0 + 3) / 2 = 1, nums[1] = 3
  Since 3 > 2, update end = mid - 1 = 0

• start = 0, end = 0

• mid = (0 + 0) / 2 = 0, nums[0] = 1
  Since 1 < 2, update start = mid + 1 = 1

• Now, start = 1, end = 0 → loop exits

• Return start = 1

Output: 1

Conclusion

This problem is a variation of classic binary search. Instead of returning -1 when the element is not found, we return the position where the target can be inserted to maintain the sorted order. The loop invariant ensures that after termination, the start pointer points to the correct insertion index.

This implementation provides both efficiency and correctness using the binary search template with slight modification in the return logic.