Search Insert Position

easyBinary Search12 stepsJava · Python · C++

Return the index of target, or where it would be inserted to keep the array sorted. That's the first index whose value is ≥ target (the lower bound). Binary search with a half-open window [lo, hi) finds it directly.

▶ Watch the animated trace

Traced input: nums = [1, 3, 5, 6], target = 5 → 2. Original problem: neetcode.io/problems/search-insert-position

Complexity

BestO(log n)

AverageO(log n)

WorstO(log n)

SpaceO(1)

Always about log₂(n) halvings.

Key idea

Answer = first index i with nums[i] >= target; it can be n (insert at the end).
If nums[mid] < target, the answer is right of mid: lo = mid + 1.
Otherwise mid might be the answer: hi = mid.
When lo == hi, that's the answer.

Common mistakes

Starting with hi = n - 1 can't return n for targets larger than everything.
Mixing closed and half-open window rules.

Solution

Java

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

Python

def searchInsert(nums: List[int], target: int) -> int:
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

C++

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

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Insert in the middle 2 goes before 3.	`nums = [1, 3, 5, 6], target = 2`	`1`
Insert at the end The lower bound is n, past the last index.	`nums = [1, 3, 5, 6], target = 7`	`4`
Insert at the front Everything is ≥ 0.	`nums = [1, 3, 5, 6], target = 0`	`0`
Single element Found at index 0.	`nums = [1], target = 1`	`0`