Lab 07 — Binary Search Fundamentals

Goal

Master the half-open invariant [lo, hi), the overflow-safe midpoint, the lower-bound / upper-bound generalizations, and the discipline that makes binary search bug-free. The deliverable: implement Search Insert Position cleanly and explain why your loop terminates.

Background Concepts

Sorted arrays; monotone predicates; loop invariants; integer overflow on (lo + hi) / 2. Review the Sorted Arrays / Sorted Sets section of the Phase 1 README.

Interview Context

Binary search is asked at every FAANG and is the #1 source of “I solved it but had off-by-one bugs” complaints. The signal isn’t whether you can find an exact match — it’s whether you can correctly answer “first index where predicate flips from false to true” in one of three loop variants without bugs. Lower-bound and upper-bound are the general tools.

Problem Statement

Given a sorted array nums of distinct integers and a target target, return the index where target is found, or the index where it would be inserted to keep nums sorted.

This is exactly lower_bound (first index i such that nums[i] >= target).

Constraints

  • 1 ≤ |nums| ≤ 10^4
  • -10^4 ≤ nums[i], target ≤ 10^4
  • nums is sorted ascending and contains no duplicates.

Clarifying Questions

  1. Are duplicates possible? (Per constraints, no — but the lower-bound formulation handles them: returns leftmost.)
  2. Can nums be empty? (Per constraints no, but the implementation handles it via lo = hi = 0.)
  3. Should we return len(nums) if target exceeds all elements? (Yes — it inserts at the end.)
  4. Is the result expected to be the first match or any match? (For Search Insert, lower-bound semantics: leftmost.)
  5. Recursive or iterative? (Iterative is preferred — no stack growth.)

Examples

numstargetOutput
[1, 3, 5, 6]52
[1, 3, 5, 6]21
[1, 3, 5, 6]74
[1, 3, 5, 6]00
[1]10
[]50

Initial Brute Force

Linear scan: walk the array, return the first index i where nums[i] >= target. If none, return len(nums).

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

Brute Force Complexity

O(N) time, O(1) space. For 10⁴ elements with 10⁴ queries, 10⁸ ops — borderline. Misses the entire point of “sorted.”

Optimization Path

Sorted + monotone predicate = binary search. The predicate is nums[i] >= target, monotone false → true as i increases. We want the first true index.

Three loop styles compete:

  1. Closed [lo, hi]: while lo <= hi, terminate at lo > hi.
  2. Half-open [lo, hi): while lo < hi, terminate at lo == hi. Recommended.
  3. Inclusive find-or-not-found: while lo < hi, post-loop check lo validity.

Half-open is the cleanest because the answer-pointer lo always satisfies the invariant “all indices < lo have predicate false; all indices >= hi have predicate true.” When lo == hi, that’s the boundary.

Final Expected Approach

def search_insert(nums, target):
    lo, hi = 0, len(nums)            # half-open [lo, hi)
    while lo < hi:
        mid = lo + (hi - lo) // 2    # overflow-safe
        if nums[mid] < target:
            lo = mid + 1             # predicate false → exclude mid
        else:
            hi = mid                 # predicate true → keep mid as candidate
    return lo                        # lo == hi; first true index

Data Structures Used

The input array. Three integer indices: lo, hi, mid.

Correctness Argument

Invariant: at every iteration, the answer (the smallest index i such that nums[i] >= target, or len(nums) if none) lies in [lo, hi] (closed interval over the half-open search range). Equivalently: nums[lo-1] < target (or lo == 0) and nums[hi] >= target (or hi == len(nums)).

Body: if nums[mid] < target, predicate at mid is false, so the answer is in [mid+1, hi]. We set lo = mid+1. Otherwise predicate at mid is true; the answer is in [lo, mid]. We set hi = mid. Both branches strictly shrink the range.

Termination: each iteration shrinks hi - lo by at least 1 (since mid is in [lo, hi-1]). Loop exits when lo == hi. Invariant gives us: lo is the answer.

Complexity

O(log N) time. O(1) space.

Implementation Requirements

  • Use lo + (hi - lo) // 2, never (lo + hi) // 2 — integer overflow in Java/C++/Go for large ints.
  • Half-open [lo, hi) with hi = len(nums) initial.
  • Loop condition lo < hi.
  • Update lo = mid + 1 (exclude mid); hi = mid (include mid as candidate).
  • Return lo.
  • Don’t write three nested if/else — there are only two branches.

Tests

  • Smoke: the table above.
  • Unit: target equals an existing element; target less than all; target greater than all; single-element array (target equal, less, greater).
  • Edge: empty array → return 0.
  • Large: N = 10⁵, sorted; binary search with random targets. Time should be sub-millisecond.
  • Random: generate sorted random arrays; cross-check against linear scan.
  • Invalid: array not sorted (undefined behavior; if defensive, assert).

Follow-up Questions

  • “Find the last index where the predicate is true (upper-bound).” → flip the predicate; or use bisect.bisect_right.
  • “Search in a rotated sorted array.” → modify the comparison: identify which half is sorted.
  • “Search for a peak element.” → ternary-search-like: compare mid with mid+1.
  • “First bad version (the predicate is the only oracle).” → same exact loop with is_bad(mid) as the predicate.
  • “Search a 2D matrix.” → flatten conceptually if rows are sorted continuations; else two passes.
  • “Why does lo + (hi - lo) // 2 matter in Python?” → it doesn’t (Python ints are unbounded), but it’s the universal idiom.

Product Extension

A timestamp-indexed log store. Find the first log line at or after a given timestamp: that’s lower_bound. The same primitive powers range queries (lower_bound(start) to upper_bound(end)) and is the basis for B-tree leaf-node lookups. Library functions like bisect, lower_bound, Arrays.binarySearch already implement this; a senior engineer reaches for them, not for a hand-rolled loop.

Language/Runtime Follow-ups

  • Python: bisect.bisect_left(nums, target) is the library answer. Returns exactly the lower-bound index.
  • Java: Arrays.binarySearch(arr, target) returns either the match index or -(insertion_point) - 1. Decode with result < 0 ? -result - 1 : result. Note the bit-shift idiom (lo + hi) >>> 1 for unsigned-right-shift to avoid overflow.
  • Go: sort.SearchInts(arr, target) returns the lower-bound directly.
  • C++: std::lower_bound(v.begin(), v.end(), target) - v.begin(). Returns an iterator; subtract begin() for the index.
  • JS/TS: no library. Must implement.
  • Overflow: Java/C++ ints are 32-bit by default. (lo + hi) can overflow when both ~2³⁰. Use the safe form.

Common Bugs

  1. (lo + hi) // 2 overflow in Java/C++/Go (32-bit ints). Use lo + (hi - lo) // 2 or >>> 1.
  2. Wrong update direction — lo = mid (instead of mid + 1) on the false branch. Causes infinite loop when lo + 1 == hi.
  3. Closed-interval while lo <= hi with half-open updates — mixing the two styles. Pick one and stick to it.
  4. Returning mid instead of lo — mid is wherever the loop happens to stop, not the answer.
  5. Off-by-one on the initial hi — hi = len(nums) - 1 for closed; hi = len(nums) for half-open.
  6. Forgetting the empty-array case — half-open form handles it naturally (lo = hi = 0); closed form needs an explicit check.

Debugging Strategy

  • Print lo, hi, mid, and nums[mid] each iteration. The range should strictly shrink.
  • If you hit an infinite loop, you almost certainly have lo = mid (not mid + 1) on the false branch.
  • For random testing, compare against bisect.bisect_left as the reference.

Mastery Criteria

  • Wrote the half-open form from memory in under 2 minutes, no off-by-ones.
  • Stated the invariant aloud: “all indices < lo are false; all indices ≥ hi are true.”
  • Identified the overflow trap and used the safe midpoint.
  • Recognized that Search Insert Position is lower_bound.
  • Knew the library function in Python, Java, Go, C++.
  • Solved a follow-up (rotated sorted array OR upper-bound) in under 10 minutes by reusing the same skeleton.