Search Insert Position

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

Constraints

• 1 <= nums.length <= 10⁴
• -10⁴ <= nums[i], target <= 10⁴
• nums contains distinct values sorted in ascending order.

Left Pointer as Insertion Index

If the target is in the array, standard binary search will find it and return its index. If the target is missing, the binary search loop will terminate when left > right. At this point, the left pointer will have advanced past all elements smaller than target and will reside at the exact index where the target should be inserted. This allows us to return left as the final result in all search cases.

Solution 1: Binary Search Insertion Index

Standard binary search returning the left boundary index upon loop termination.

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int 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; // left is the insertion index
    }
}

class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
                
        return left  # left is the insertion index

#include <vector>

class Solution {
public:
    int searchInsert(std::vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 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; // left is the insertion index
    }
};

Complexity Analysis

• Time Complexity: O(log n) since we half the search range at each step.
• Space Complexity: O(1) auxiliary space as we use a fixed number of index variables.

Where It Breaks

If the array is unsorted, index locations cannot be resolved using binary search, and a linear scan is required, increasing complexity to O(n).

Common Mistakes

• Incorrect insertion pointer: Returning right instead of left after loop termination. right will point to the largest element smaller than the target, which is off-by-one from the correct insertion location.
• Handling boundaries poorly: Returning 0 or nums.length by default instead of the current state of the pointers.

Frequently Asked Questions

Why return left instead of right? When the loop terminates, the pointers have crossed: right resides at the index of the element immediately smaller than the target, and left resides at the index of the element immediately larger than the target. Inserting at left shifts the larger elements to the right, preserving sorted order.

Does this handle target values larger than the entire array? Yes. If target is larger than all elements, the left pointer will advance to index n and return n, which is the correct insertion index at the end of the array.

← All Problems