Binary Search Done Correctly: Invariants Over Memorization

If you interview at Google, Amazon, Microsoft, expect some version of "Binary Search". It is rated Easy, and it falls squarely into the Modified Binary Search pattern — pattern-first preparation beats grinding random problems every time. Part 1 of 11 in the Modified Binary Search arc.

The Problem

Given a sorted integer array nums and a target, return its index or -1. Knuth's observation still holds: the idea is simple, the details are treacherous. Off-by-ones here cascade through every harder question in this arc, which is why interviewers still ask the basic version.

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 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.

Sorted input, O(log n) expectation — but the real skill being tested is stating an invariant: the target, if present, always lies within [lo, hi]. Every line of the loop must preserve it, and every variant in this arc is a different invariant.

The Approach

Closed-interval template: lo, hi = 0, n - 1; loop while lo is at most hi; compare the middle; shrink to the half that preserves the invariant, always excluding mid itself. Termination is guaranteed because the interval strictly shrinks every iteration.

(lo + hi) // 2 cannot overflow in Python — say it anyway, because interviewers calibrated on C++ and Java expect you to know why they write lo + (hi − lo) / 2.

Python Solution

def binary_search(nums: list[int], target: int) -> int:
    """Index of target in sorted nums, or -1. Closed-interval template."""
    lo, hi = 0, len(nums) - 1
    while lo <= hi:                    # invariant: target in [lo, hi] if present
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1               # mid is too small: exclude it
        else:
            hi = mid - 1               # mid is too large: exclude it
    return -1

Complexity

• Time: O(log n) — the search interval halves every iteration
• Space: O(1) — three integers

Interview Tips and Follow-Ups

• Commit to one template (closed interval here; half-open [lo, hi) is equally valid) and use it for every problem — mixing templates is where bugs breed.
• Both mid + 1 and mid - 1 must exclude mid, or a two-element array infinite-loops. That is the classic screen failure.
• Python's bisect module implements the boundary variants — usable in interviews if you can explain what it returns, which is the next question in this arc.

That wraps part 1 of the Modified Binary Search arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.