Search Insert Position
Find where a target is, or where it would belong — the binary search that returns a boundary
Problem Statement
Given a sorted array of distinct integers and a target, return the index where the target is found. If it is not present, return the index where it would be inserted to keep the array sorted.
You must write an O(log n) algorithm.
Input: nums = [1, 3, 5, 6], target = 5
Output: 2 (found at index 2)
Input: nums = [1, 3, 5, 6], target = 2
Output: 1 (2 belongs between 1 and 3)
Input: nums = [1, 3, 5, 6], target = 7
Output: 4 (7 belongs past the end)Intuition
This is Binary Search with a better failure mode. Instead of returning -1 when the target is absent, it returns the position where it belongs.
The key insight
When a standard binary search finishes without a match, lo has landed on exactly the right answer.
The loop's invariant is: everything left of lo is < target, and everything right of hi is > target. When lo > hi the range is empty, and lo sits precisely at the first element that is not less than the target — which is where an insertion goes.
So the code is the same loop; only the final return changes. That is the whole problem.
The insertion point is a boundary
Reframe the array as a yes/no question — "is this element >= target?":
nums = [1, 3, 5, 6], target = 2
>= 2 ? no yes yes yes
0 1 2 3
↑
first "yes" — the answerBecause the array is sorted, the answers are always a run of nos followed by a run of yeses. Binary search finds that flip point. This is the lower bound pattern, and it is the single most reusable form of binary search.
Watch it run
Approach
Run the standard binary search
lo = 0, hi = n - 1, loop while lo <= hi.
Shrink as usual
nums[mid] < target → lo = mid + 1. Otherwise hi = mid - 1.
Return lo after the loop
Not -1. lo is the insertion point.
Solution
def search_insert(nums: list[int], target: int) -> int:
"""Index of target, or the index where it would be inserted."""
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return lo # the loop ends with lo at the insertion pointThe pure lower-bound form, which drops the equality check entirely:
def search_insert_lower_bound(nums: list[int], target: int) -> int:
lo, hi = 0, len(nums) # hi is EXCLUSIVE here
while lo < hi: # note: < , not <=
mid = lo + (hi - lo) // 2
if nums[mid] < target:
lo = mid + 1
else:
hi = mid # keep mid as a candidate
return loInclusive and exclusive templates do not mix
The two versions above use different conventions and each is internally consistent:
- Inclusive
hi = n - 1pairs withwhile lo <= hiandhi = mid - 1. - Exclusive
hi = npairs withwhile lo < hiandhi = mid.
Borrowing one line from the other template is how infinite loops and off-by-ones appear. Pick one and keep every line consistent with it.
Complexity Analysis
Time Complexity
O(log n)
Space Complexity
O(1)
- Time — the search space halves every iteration.
- Space — a handful of integers.
Edge Cases
Related Problems
- Binary Search — the same loop returning
-1on a miss - First Bad Version — the same boundary search, without an array
- H-Index — sorted data where a boundary defines the answer