Search Insert Position

Medium · rating 1050 · Binary Search, Arrays

The first line contains n space-separated integers, sorted ascending with no duplicates. The second line contains a target. Print the index where the target is found, or the index where it would be inserted to keep the array sorted.

Editorial

Search Insert Position is a fundamental binary search interview problem: in a sorted array return the index of a target, or the index where it would be inserted to keep the array sorted.

Approach

Binary-search for the target; when it's absent, the stopping point lo is exactly the insertion index — the number of elements strictly less than the target. This is the reusable lower-bound pattern.

lo, hi = 0, len(nums)
while lo < hi:
    mid = (lo + hi) // 2
    if nums[mid] < target: lo = mid + 1
    else: hi = mid
return lo

Complexity

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

Related problems

Open Search Insert Position in Code Arena →