Given a sorted (ascending) slice of distinct integers and a target, return the index
where the target is, or where it would be inserted to keep the slice sorted. This
is the leftmost index i with nums[i] >= target (or len(nums) if the target is
larger than everything).
searchInsert(nums, target)
Input format: nums | target.
[1, 3, 5, 6], target=5 // → 2
[1, 3, 5, 6], target=2 // → 1
[1, 3, 5, 6], target=7 // → 4
This isn't quite "find the target" — it might not be present, and you need where it would insert. Every element is either strictly less than the target, or greater-or-equal, and since the array is sorted, all the "less than" elements come first. The insertion point is exactly the boundary where "greater-or-equal" starts.
Imagine testing, for every index, "is nums[i] >= target?" Since the array is sorted, this is false for a prefix and true for the rest — it flips exactly once. Binary search's job here is "find where a monotonic condition flips from false to true," a more general framing than "find this exact number."
A linear scan checking each element would also find the boundary, but takes time proportional to the array's length. Since the condition never flips back once true, you can halve instead of scanning.
Maintain [lo, hi] with the invariant: the boundary is somewhere in [lo, hi+1]. Look at the middle: if it's >= target, the boundary is at or before it, so pull hi to mid - 1. If it's < target, the boundary is strictly after, so push lo to mid + 1.
When the range empties, lo has converged on the first index where the condition became true. If every element is < target, lo ends up equal to the array's length — correctly "insert at the end."
"Find the boundary of a monotonic condition" is binary search's real power — applying to any yes/no test that's false-then-true across a sorted range, letting you find the flip in logarithmic time instead of scanning.
def search_insert(nums, target):
lo = 0
hi = len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] >= target:
hi = mid - 1
else:
lo = mid + 1
return lo
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.