DSA Search Insert Position

The problem

The insert position of a target is the index where it belongs in a sorted list to keep the order. Inserting at that index leaves the list sorted. Every value before the index is smaller than the target.

That first fitting index is called the lower bound. A present target answers its own index. An absent target answers the slot between its neighbours.

nums = [1, 3, 5, 6]
cases = [(5, 2), (2, 1), (7, 4), (0, 0)]
for target, expected in cases:
    print("target", target, "insert position:", expected)

Read one row at a time. The target 7 is larger than every value, so it answers 4, the list length. The target 0 is smaller than every value, so it answers 0.

Intuition: scan until a value fits

The first idea scans from the left. The scan stops at the first value that is not smaller than the target. That value's index is the answer.

The idea is correct on sorted data. Its cost is the trap. A target near the end forces the scan past nearly the whole list, and a long list makes that walk long.

def scan_position(nums, target):
    steps = 0
    for i, value in enumerate(nums):
        steps += 1
        if value >= target:
            return i, steps
    return len(nums), steps

nums = list(range(0, 200, 2))
position, steps = scan_position(nums, 198)
print("list length:", len(nums))
print("position:", position)
print("values scanned:", steps)
position, steps = scan_position(nums, 2)
print("early target position:", position, "- values scanned:", steps)

The same method costs 100 scans for one target and 2 for another. The price depends on the answer's position. A method whose price ignores position entirely appears in section 4.

Brute force: the scan as a function

The brute force is the scan, written plainly. One counter charges one unit per value examined. The function returns the first index whose value is not less than the target, or the list length when no value qualifies.

def insert_brute(nums, target):
    steps = 0
    for i, value in enumerate(nums):
        steps += 1
        if value >= target:
            return i, steps
    return len(nums), steps

nums = [1, 3, 5, 6]
for target in [5, 2, 7, 0]:
    position, steps = insert_brute(nums, target)
    print("target:", target, "position:", position, "steps:", steps)

Even on four values, an unlucky target costs three scans. The count is small only because the list is small. Section 2 showed the same method at length 100.

The optimal solution: halve the range until it closes

The lower bound is the first index whose value is not less than the target, and halving a lo-hi range until the two meet lands exactly on that index. That one sentence is the whole method.

The range starts as the whole list, with hi one past the last index. Each step examines the middle value. A middle value smaller than the target moves lo past it, and any other middle value pulls hi down to it.

def lower_bound(nums, target):
    lo = 0
    hi = len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

nums = [1, 3, 5, 6]
cases = [(5, 2), (2, 1), (7, 4), (0, 0)]
for target, expected in cases:
    result = lower_bound(nums, target)
    print("target", target, "-> position", result, "expected:", expected, "match:", result == expected)

All four cases from the start of the article pass. The loop ends when lo equals hi. That meeting point is the answer, with no separate found flag anywhere.

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

The target 2 is absent. Its neighbours are 1 and 3. The walk below prints the range before each halving step, so the closing range stays visible.

nums = [1, 3, 5, 6]
target = 2
lo = 0
hi = len(nums)
step = 0
while lo < hi:
    mid = (lo + hi) // 2
    step += 1
    print("step", step, "- lo:", lo, "hi:", hi, "mid:", mid, "value:", nums[mid])
    if nums[mid] < target:
        lo = mid + 1
    else:
        hi = mid
print("position:", lo)

The middle value 5 is not less than 2, so hi drops to its index. The middle value 3 is also not less than 2, so hi drops again. The range closes at index 1, between 1 and 3, exactly where 2 belongs.

Complexity

Each halving step discards half of the remaining range, so a list of n values needs about log2 of n steps, giving O(log n) time. The scan needs up to n steps, giving O(n) time.

The halving search stores three index variables and nothing else, so its extra space is O(1). The scan uses the same constant space, which is why the contest between them is purely about steps.

def halving_steps(nums, target):
    lo = 0
    hi = len(nums)
    steps = 0
    while lo < hi:
        mid = (lo + hi) // 2
        steps += 1
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return steps

def scan_steps(nums, target):
    steps = 0
    for value in nums:
        steps += 1
        if value >= target:
            break
    return steps

for n in [4, 100, 1000]:
    nums = list(range(0, 2 * n, 2))
    target = 2 * n - 2
    print("values:", n, "- scan steps:", scan_steps(nums, target), " halving steps:", halving_steps(nums, target))

Counts beat clocks here. A thousand values cost the scan a thousand steps and cost the halving search ten. Each doubling of the list adds exactly one halving step.

Edge cases and pitfalls

An empty list answers 0. The range starts empty, the loop never runs, and lo is already the only possible slot. No special case handles it.

A target equal to an existing value answers that value's first index when duplicates exist. The not-less-than test pulls hi down onto the earliest copy. Changing the test to less-or-equal would slide the answer past every copy instead.

def lower_bound(nums, target):
    lo = 0
    hi = len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

print("empty list:", lower_bound([], 5))
print("below all:", lower_bound([1, 3, 5, 6], 0))
print("above all:", lower_bound([1, 3, 5, 6], 7))
print("single value, target smaller:", lower_bound([4], 2))
print("single value, target equal:", lower_bound([4], 4))
print("single value, target larger:", lower_bound([4], 9))
print("duplicates, first slot:", lower_bound([1, 2, 2, 2, 3], 2))

The duplicates row is the definition made visible. The lower bound is the first index whose value is not less than 2. That index holds the first of the three copies.