Search Insert Position
Search Insert Position: in a sorted array of distinct integers, return the index of target, or the index where it would be inserted to keep the array sorted — in O(log n).
- 1 <= nums.length <= 10⁴
- -10⁴ <= nums[i] <= 10⁴
- nums contains distinct values sorted in ascending order
- -10⁴ <= target <= 10⁴
Intuition
Both questions have the same answer: the number of elements strictly less than target. If the target is present that count is its index; if it is absent that count is exactly where it belongs. So instead of searching for a value and handling a miss separately, search for a boundary — the first position whose element is at least target — and the found and not-found cases collapse into one return.
Whenever a sorted array question asks where does this go rather than is this here, it is a lower-bound search. The signal is that a miss still needs a meaningful index. The same boundary search underlies First Bad Version, Find First and Last Position, and Koko Eating Bananas.
Approach
Before reading on: note that the answer equals the count of elements strictly less than the target, in both the present and absent cases. Then set up a half-open interval and decide which side keeps mid as a candidate. Check what your bounds return when the target exceeds every element.
Search for a boundary, not a value
Classic binary search asks is this the element? and returns -1 when it never is. That leaves the insertion case unanswered. Reframe it: the array is split into a prefix of elements < target and a suffix of elements >= target, and the answer is the index where that split occurs. This is the lower-bound query. Because the array is sorted, the predicate nums[i] >= target is false-then-true across the array, and binary search on a monotone predicate finds the first true in O(log n).
The half-open interval that makes it terminate
Keep lo = 0 and hi = len(nums) — note hi is one past the last index, not the last index. The invariant is that the answer lies in [lo, hi]. At each step take mid = (lo + hi) // 2; if nums[mid] < target the boundary is strictly right of mid, so lo = mid + 1, otherwise mid itself may still be the answer, so hi = mid. The interval strictly shrinks every iteration because mid < hi always holds, which guarantees termination. When lo == hi the interval holds one candidate and that is the answer.
Why hi = len(nums) rather than len(nums) - 1
If target is larger than every element, the correct answer is len(nums) — appended at the end. An interval initialised to len(nums) - 1 can never return that index, so the greater-than-everything case is wrong by construction. Setting hi one past the end makes that a representable answer rather than a special case. This is also why the loop is while lo < hi with no equality: the search space is half-open, and lo == hi means it is empty and settled. Time is O(log n), space O(1).
Solution & live demo
Common pitfalls
Initialising hi to len(nums) - 1
lo, hi = 0, len(nums) - 1
lo, hi = 0, len(nums)
The answer can legitimately be len(nums) when the target exceeds every element. With hi capped one lower that index is unreachable, so [1,3,5] with target 7 returns 2 instead of 3.
Using lo <= hi with a half-open interval
while lo <= hi:
...
hi = midwhile lo < hi:
...
hi = midMixing the closed-interval condition with the half-open update hi = mid never shrinks the range when lo == hi == mid, so the loop spins forever. The condition and the updates must belong to the same convention.
Returning -1 on a miss
if nums[mid] == target:
return mid
return -1return lo
The question asks for the insertion point, not a presence test. Searching for equality throws away the boundary information the search already computed, and -1 is never a valid answer here.
Edge cases
The predicate is true at index 0, so 0 is returned.
No element satisfies the predicate, lo walks to len(nums) = 3.
Lower bound lands on the element itself, since distinctness means only one match.
One comparison decides between index 0 and index 1.
Returns 1, the first index holding a value at least 2.