Search Insert Position

Problem Statement

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

Example

Input:  nums = [1,3,5,6], target = 2
Output: 1
Explanation: 2 would be inserted at index 1.

Approach

This is the lower bound: the first index whose value is >= target. Use a half-open window [left, right); when nums[mid] < target move left up, otherwise move right down. The final left is the answer.

Complexity

• Time: O(log n)
• Space: O(1)

Solution Code

Python

def searchInsert(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

Java

int searchInsert(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}

C++

int searchInsert(vector<int>& nums, int target) {
    int left = 0, right = (int)nums.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}

Key Takeaways

• This is the classic lower_bound template (first value >= target).
• The half-open window [left, right) avoids off-by-one errors.
• Reference: LeetCode 35 (Search Insert Position); C++ std::lower_bound.