Search Insert Position

This is the classic binary search with one twist: when the target is missing, you must say where it would be. Interviewers like it as a warm-up because it looks trivial, and the twist tests whether you understand what left and right mean when the loop stops.

It is also a real operation. Keeping a list sorted as new values arrive — a leaderboard, a price ladder, a sorted index — needs exactly this answer on every insert.

The problem

You are given a list of distinct integers sorted in increasing order, and a target. If the target is in the list, return its index. If it is not, return the index where it would have to be inserted to keep the list sorted.

• nums = [1, 3, 5, 7, 9, 11, 13, 15], target = 11 → 5. The value 11 sits at index 5.
• Same nums, target = 8 → 4. 8 belongs between 7 (index 3) and 9 (index 4), so it would take index 4 and push 9 to the right.

Constraints: 1 ≤ len(nums) ≤ 10⁴, values and target between -10⁴ and 10⁴, all values distinct, and the solution must run in O(log n).

Clarifying questions

• Can values repeat? No, they are distinct. (If they could, you would want the first matching index, and that changes the template. See the follow-ups.)
• What if the target is bigger than everything? Return len(nums): it goes at the end.
• Can the list be empty? The constraints say no, but the solution should return 0 anyway.
• Do you want the index or the value? The index.

Approach 1: the simple way

Walk from the left and stop at the first value that is not smaller than the target. That is either the target itself or the first value bigger than it, and in both cases its index is the answer.

1def search_insert_linear(nums: list[int], target: int) -> int:2    """Index of target, or where it would go: O(n) scan."""3    for i, value in enumerate(nums):4        if value >= target:                  # first value not smaller than target5            return i6    return len(nums)                         # target is bigger than everything

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

One scan of 10,000 values is fast. The trouble is that the problem demands O(log n), and it demands it for a reason: this operation usually runs once per insert. With 10⁵ values and 10⁵ inserts, a linear scan costs 10¹⁰ steps. Binary search costs about 17 × 10⁵, less than two million.

The key insight

The insert position is the first index whose value is at least the target. That is a boundary, and the values are sorted, so the test "is nums[i] >= target?" reads no, no, …, yes, yes. Binary search finds boundaries.

You do not even need a new template. Run the exact-match template from the core lesson. If it finds the target, return that index. If it does not, left is already the insert position when the loop stops. Here is why.

Watch what the two updates promise:

• left = mid + 1 happens only when nums[mid] < target. So every index before left holds a value smaller than the target.
• right = mid - 1 happens only when nums[mid] > target. So every index after right holds a value bigger than the target.

Both promises are true at the start (nothing is before index 0 or after the last index) and stay true after each step. The loop ends when left > right, and because each step moves a bound past mid by exactly one, it ends with right == left - 1. The two regions now touch: everything before left is smaller than the target, and everything from left on is bigger. The target belongs exactly at left.

That argument is worth saying in the interview. It turns "return left" from a memorised trick into something you proved.

Approach 2: binary search, and return left

1def search_insert(nums: list[int], target: int) -> int:2    """Index of target in sorted nums, or the index where it would be inserted."""3    left, right = 0, len(nums) - 14    # invariant: everything before left is < target, everything after right is > target5    while left <= right:6        mid = left + (right - left) // 27        if nums[mid] == target:8            return mid9        if nums[mid] < target:10            left = mid + 111        else:12            right = mid - 113    return left                              # right == left - 1: left is the first value > target

Dry run on nums = [1, 3, 5, 7, 9, 11, 13, 15], target = 11:

The first step throws away indices 0 to 3 in one comparison. The second finds the target.

Now target = 8, which is missing:

At the end, right = 3 and left = 4. Index 3 holds 7, smaller than 8; index 4 holds 9, bigger than 8. The target goes at 4.

Time: O(log n) — the range halves each step, so at most 14 steps for 10⁴ values. Space: O(1).

Approach 3: the boundary template, or the library

Because the answer is a boundary, the half-open template from the core lesson also solves it directly: the answer is lower_bound(nums, target), the first index with nums[i] >= target. Python has it built in:

1from bisect import bisect_left234def search_insert_library(nums: list[int], target: int) -> int:5    """Same answer from the standard library."""6    return bisect_left(nums, target)

All three versions were run against each other on 300 random sorted lists and targets, and they agree. Which to show? Write Approach 2 or the boundary template by hand, then mention bisect_left as what you would use in production code. The two hand-written versions are equally good here; the boundary version is the one that keeps working when duplicates are allowed.

Edge cases

• Target smaller than everything: every comparison moves right left, the loop ends with left = 0, and 0 is correct.
• Target larger than everything: every comparison moves left right, the loop ends with left = len(nums). That is a valid answer, not an index error, because the function never reads nums[left] after the loop.
• Empty list: right = -1, the loop never runs, and the function returns 0.
• One element: left == right == 0, so the <= test runs one comparison. With < this case would be skipped.
• Duplicates (if allowed): the exact-match branch returns some matching index, not necessarily the first. Use the boundary version.

Follow-ups

• "Values can repeat; return the first position." Use the boundary template: right = len(nums), while left < right, right = mid when nums[mid] >= target. That is bisect_left.
• "Insert after any equal values." Change the test to nums[mid] > target. That is bisect_right, and it keeps equal items in arrival order.
• "The list is too large to know its length" (you can only read nums[i], which fails past the end). Double a bound — 1, 2, 4, 8… — until it passes the target or the end, then binary search inside the last gap. That costs O(log p), where p is the answer's position.