Search Insert Position and the Lower Bound Idiom

"Search Insert Position" shows up again and again in Amazon, Microsoft, Apple phone screens. It is a Easy problem on paper, but the real test is whether you recognize the Modified Binary Search pattern quickly and code it cleanly. Part 2 of 11 in the Modified Binary Search arc.

The Problem

Given a sorted array of distinct integers and a target, return the index if found, or the index where it would be inserted to keep order. This is lower_bound — the single most reusable binary search variant, and the direct answer to a whole family of screen questions.

Input:  nums = [1, 3, 5, 6], target = 5
Output: 2
For target = 2 the answer is 1; for target = 7 it is 4.

Recognizing the Modified Binary Search Pattern

Binary search is not about sorted arrays — it is about any monotonic predicate: if the answer space splits into a false-region followed by a true-region, you can halve it. FAANG interviews rarely ask the textbook version; they ask rotated arrays, boundary-finding, and search-on-the-answer problems where the array being searched is conceptual. Getting the loop invariant right is the whole game.

Insert position means boundary, not membership: the first index whose value is at least the target. Boundary searches use the half-open template where lo converges to the boundary rather than a found element — a different invariant from plain search, and the source of most confusion.

The Approach

Half-open [lo, hi) with hi = n. While the range is non-empty, test mid: values below target push lo = mid + 1; values at or above pull hi = mid. When the range empties, lo is the first at-least-target index — which is simultaneously the found index and the insert position, with no special cases.

Note hi = mid, not mid − 1: mid might be the boundary, so it stays in range. That asymmetry is the whole template.

Python Solution

def search_insert(nums: list[int], target: int) -> int:
    """Index of target, or where it would be inserted (lower bound)."""
    lo, hi = 0, len(nums)              # half-open [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid                   # mid may be the answer: keep it
    return lo

Complexity

• Time: O(log n) — halving over the half-open range
• Space: O(1) — index arithmetic only

Interview Tips and Follow-Ups

• This is bisect.bisect_left. Being able to reimplement the stdlib and say so is exactly the right flex level.
• Upper bound (first index strictly greater) differs by one comparison — the pair together solves First and Last Position, next in this arc.
• Why no equality check in the loop? Because boundaries, not matches, are the target — expect the interviewer to probe this.

More Modified Binary Search problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.