Search Insert Position

You'll write binary search in a form that's hard to get wrong: find the first position where a yes/no test turns true. You need sorted lists and index ranges. Related chapter: binary search.

1. The problem

You get a sorted list of distinct integers and a target. If the target is in the list, return its index. Otherwise, return the index where it would go to keep the list sorted. Return only the index; don't change the list. This is Search Insert Position (LC 35).

LeetCode never passes an empty list, but our function returns 0 for one. Numbers can be negative. The answer can equal the list's length, as in the third example, so it isn't always an existing index.

2. A correct baseline

Walk until the first number at least as large as the target. If there isn't one, the answer is the end of the list.

def baseline(nums, target):
    for i, number in enumerate(nums):
        if number >= target:
            return i
    return len(nums)

assert baseline([1, 3, 5, 6], 5) == 2
assert baseline([1, 3, 5, 6], 2) == 1
assert baseline([1, 3, 5, 6], 7) == 4
assert baseline([], 4) == 0

This takes O(n) time: the work grows in step with the list. On a million numbers, that's up to a million comparisons. It uses O(1) extra space.

The bottleneck. It checks every smaller number one by one. In a sorted list, one comparison can rule out half the positions at once.

3. The observation

Ask "is nums[i] >= target?" at every position. For [1, 3, 5, 6] and target 2, the answers are [False, True, True, True]. Because the list is sorted, the answers are always some Falses followed by some Trues. We want the first True, or n if they're all False.

Look at the middle position. If its number is too small, everything to its left is too small too, so search the right half. Otherwise, the middle might be the first True, so keep it and search the left half. Finding the target itself needs no special case: it's the first True.

4. The solution and a trace

class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        """For sorted distinct integers, return the target's insertion index."""
        left = 0
        right = len(nums)
        # Values before left are too small; values at or after right are large enough.
        while left < right:
            middle = (left + right) // 2
            if nums[middle] < target:
                left = middle + 1
            else:
                right = middle
        return left

solve = Solution().searchInsert
assert solve([1, 3, 5, 6], 5) == 2
assert solve([1, 3, 5, 6], 2) == 1
assert solve([1, 3, 5, 6], 7) == 4
assert solve([], 4) == 0

right starts one past the last index. The code never reads nums[right]: middle always falls between left and right − 1.

Trace target 2 in [1, 3, 5, 6]:

5. Why it works

What stays true. Every number before left is smaller than the target. Every number at or after right is at least the target. Sorted order keeps this true after each update.

The answer is right. The loop ends when left and right meet. That spot is the first position whose number is large enough, or n if there's none. That's exactly the target's index, or where it would go.

The loop always ends. Both branches shrink the range. left = middle + 1 skips a position we know is False. right = middle keeps a position that might be the answer. Writing left = middle instead could loop forever when one position is left.

6. Cost, edge cases, and failure

Cost. The range halves each step: O(log n) time. On a million numbers, that's about 20 comparisons. O(1) extra space.

Edge cases. A target smaller than everything returns 0. A target larger than everything returns n. An empty list skips the loop and returns 0. With repeated values, this returns the first match, though LeetCode promises distinct values.

Where it fails. On an unsorted list, the Falses and Trues no longer split cleanly:

assert solve([3, 1, 2], 3) == 3  # Deliberately invalid input: 3 already exists at index 0.
assert baseline([3, 1, 2], 3) == 0

Neither function promises anything on unsorted input. The example shows why binary search can't find values in an unsorted list.

import random
rng = random.Random(35)
for _ in range(1500):
    nums = sorted(rng.sample(range(-30, 31), rng.randrange(25)))
    target = rng.randint(-35, 35)
    before = nums.copy()
    position = solve(nums, target)
    assert position == baseline(nums, target)
    assert all(value < target for value in nums[:position])
    assert all(value >= target for value in nums[position:])
    assert nums == before