Binary Search I — The Template

Review boundary and corrected contracts

Separate the half-open predicate domain [lo,hi) from the inclusive candidate boundary range [lo,hi]. The initial hi is a sentinel if no predicate is true and must never be indexed. target+1 for upper_bound is an integer-specific reduction.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Where the theory lives

If the underlying data structure feels shaky, the from-scratch explanation for binary search is in the 6-month plan: S032 — theory.

Learning objective: Own one binary search template cold: the bisect-left 'first index where a predicate is true' form, with a loop invariant that guarantees termination and no off-by-one.

Series: LeetCode — From Basics to Production-Ready · Session 13 / 65 · Phase 1 · Core patterns

Prerequisites. None beyond a sorted list and integer arithmetic. This is the foundation for L14 (rotated/2D) and L15 (binary search on the answer), so learn the one template here until it's automatic.

Watch first

Optional companions from the original reading list (not prerequisites):

• Binary Search — the clean template: compare its endpoint convention with the invariant below.
• Binary Search — the definitive framework: focus on the predicate boundary.
• Binary Search full lecture: distinguish lower and upper bounds.

The lesson and exercises below are self-contained; external video availability is not verified here.

What this pattern IS

You have a sorted array and want to find where a value is (or where it would go). Scanning left to right is O(n). Binary search exploits the sortedness: look at the middle element; because the array is sorted, that one comparison tells you which half the answer is in, so you throw the other half away. Halving the search space each step gives O(log n) — 20 steps for a million elements, 30 for a billion.

The idea is trivial. The bugs are not. Binary search is notorious for three failure modes:

1. Infinite loops — the range never shrinks because mid lands on a boundary you don't move past.
2. Off-by-one — you return mid, mid − 1, or mid + 1 and can't remember which.
3. Overflow — (low + high) overflows in fixed-width languages (not Python, but reviewers still ask).

The cure is discipline: own exactly one template, with a crisp loop invariant, and reframe every problem as "find the first index where a monotone predicate becomes true." That single boundary-finding form solves search, insert-position, first/last occurrence, and (in L15) search-on-the-answer.

Guess the number

Real: I pick a number 1–100; you guess, I say 'higher' or 'lower'. You always guess the middle of the remaining range, halving it each time — 7 guesses max. Binary search is this game where 'higher/lower' is a comparison with the middle element.

mid = (lo + hi) // 2; if predicate(mid): hi = mid else lo = mid + 1.

First principles

Question: Why does the half-open 'first true' template always terminate and never go off by one?

The first true boundary lies in the inclusive candidate range [lo,hi]. Predicate evaluations are made only in the original half-open domain; hi can be the sentinel meaning no true position.

Because: Every step preserves this range so the answer is never discarded.

Premise: The predicate is MONOTONE: false, false, ..., false, true, true, ..., true — it changes from False to True at most once; all-False and all-True domains are allowed.

Because: Sorted data (or a monotone feasibility test) guarantees a single boundary between the false and true regions.

Premise: If predicate(mid) is true, the boundary is at mid or left of it, so set hi = mid (keep mid as a candidate).

Because: mid itself might be the first true; discarding it could lose the answer.

Premise: If predicate(mid) is false, the boundary is strictly right, so set lo = mid + 1 (discard mid).

Because: mid is known-false and can never be the first true, so excluding it is safe and guarantees progress.

Premise: The range strictly shrinks every step and stops when lo == hi.

Because: One branch does hi = mid (< hi since mid < hi when lo < hi), the other does lo = mid + 1 (> lo); either way the interval narrows, so it terminates.

Conclusion: lo == hi at the end IS the boundary: the first index where the predicate holds (or len(array) if none).

The templates

Template — the ONE to memorise: first index where predicate is true

def lower_bound(lo, hi, predicate):
    """Return the first true position in [lo, hi), or the initial hi sentinel.
    predicate must be MONOTONE: False...False, True...True.
    Returns hi if predicate is never true in range."""
    while lo < hi:                  # predicate domain is half-open; the boundary may equal hi
        mid = lo + (hi - lo) // 2   # overflow-safe midpoint (matters in C++/Java)
        if predicate(mid):
            hi = mid                # mid might be the answer -> keep it
        else:
            lo = mid + 1            # mid is too small -> discard it
    return lo                       # lo == hi == the boundary

Applying it to plain search / insert position

def search_insert(nums, target):
    # first index i where nums[i] >= target  ->  predicate(i) = nums[i] >= target
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] >= target:
            hi = mid
        else:
            lo = mid + 1
    return lo    # insertion point; nums[lo] == target if present
 
def contains(nums, target):
    i = search_insert(nums, target)
    return i < len(nums) and nums[i] == target

First and last occurrence (from the same template)

import bisect
def first_last(nums, target):
    left = bisect.bisect_left(nums, target)     # first index >= target
    right = bisect.bisect_right(nums, target)   # first index > target
    if left == len(nums) or nums[left] != target:
        return (-1, -1)
    return (left, right - 1)                     # inclusive range of target

bisect_left/bisect_right are the standard library's version of these boundary operations — use them when allowed, and know how to write them by hand when not.

Mental model

Name: Find the boundary, not the value

Picture: A row of dominoes, all False then all True. You're hunting the FIRST True. mid True → the boundary is here or left (hi = mid). mid False → boundary is strictly right (lo = mid + 1). Stop when the range collapses to one point.

• Half-open [lo, hi); loop while lo < hi; return lo.

• predicate True → hi = mid (keep candidate). predicate False → lo = mid + 1 (discard).

• mid = lo + (hi - lo) // 2 to avoid overflow.

• Reframe an ordered search this way only after establishing a monotone predicate; not every search problem has one.

Trigger: 'sorted array', 'find/insert position', 'first/last occurrence', or 'smallest x satisfying a monotone condition'.

Memory / mnemonic

Own one template by burning in a four-line shape and a rule couplet.

• The shape: while lo < hi: mid; if pred: hi = mid; else lo = mid+1; return lo. Four lines, always the same. Type it a dozen times until your fingers know it.
• The rule couplet: "True keeps mid, False kills mid." True → hi = mid (mid survives as a candidate); False → lo = mid + 1 (mid is killed).
• The midpoint rhyme: "lo plus half the gap" → lo + (hi - lo) // 2. For nonnegative indices within the signed type's maximum, the intermediate values fit too. Python integers do not overflow this way; arbitrary signed endpoints in C++/Java can still make hi - lo overflow.
• The return peg: half-open means the loop ends at lo == hi, and that point is the boundary → "return lo."

One template, memorised cold, beats three templates you half-remember and mix up under pressure.

The trap

Myth: You should use while lo <= hi with hi = mid - 1 / lo = mid + 1 and return mid — the 'classic' textbook binary search.

Truth: Closed and half-open intervals both support correct boundary searches. The bug is mixing their endpoint rules, not choosing a closed interval. This lesson standardises on half-open bounds for consistency.

Why: A closed lower-bound loop can use hi = mid - 1 on True, lo = mid + 1 on False, and return lo after the interval becomes empty; it does not need a separate best-so-far variable. Its invariant is that every original index below lo is too small and every original index above hi is large enough.

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

Test: On [2, 2, 4] with target 2, both formulations return 0; with target 5, both return 3. On the empty list both return 0. Do not substitute return mid: it may be unassigned or may not be the boundary.

What reviewers actually ask

Binary search is asked partly to see if you have a template you trust and partly to test boundary reasoning.

• Binary Search (704) · Easy · Practice selection. — probes: do you have a clean, bug-free template? Follow-up: return the insert position if absent (35).
• Search Insert Position (35) · Easy · Practice selection. — probes: lower-bound thinking (first index ≥ target). Follow-up: first index strictly greater (upper bound).
• Find First and Last Position of Element in Sorted Array (34) · Medium · Practice selection. — probes: two boundaries (bisect_left and bisect_right) in O(log n). Follow-up: count occurrences = right − left.
• First Bad Version (278) · Easy · Practice selection. — probes: binary search over a monotone predicate isBadVersion, minimising API calls. Follow-up: the overflow-safe midpoint.
• Sqrt(x) (69) · Easy · Practice selection. — probes: largest m with m*m ≤ x — binary search on the answer (previews L15). Follow-up: return more decimal places.
• Guess Number Higher or Lower (374) · Easy · Practice selection. — probes: the raw guessing game with a given oracle. Follow-up: the overflow bug in (lo + hi) // 2.

Universal probe: "is your midpoint overflow-safe, and can you prove your loop terminates?" Have both answers ready.

Worked solutions

1. Binary Search (704)

Plain words: given a sorted array and a target, return its index, or −1 if absent.

Brute force: linear scan, O(n). Insight: use the boundary template to find the first index ≥ target, then check if that slot equals target.

def search(nums, target):
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] >= target:        # predicate: value has reached target
            hi = mid
        else:
            lo = mid + 1
    return lo if lo < len(nums) and nums[lo] == target else -1

Complexity: O(log n) time, O(1) memory. Follow-up — "return insert position if absent" (LC35): just return lo without the equality check.

Goal: Rewrite to find the LAST index equal to target (or -1).

Hint: Find the first index > target (upper bound), then step back one and verify.

def searchLast(nums, target):
    lo, hi = 0, len(nums)
    while lo < hi:                     # first index where nums[mid] > target
        mid = lo + (hi - lo) // 2
        if nums[mid] > target:
            hi = mid
        else:
            lo = mid + 1
    i = lo - 1                         # step back to the last <= target
    return i if i >= 0 and nums[i] == target else -1

2. Find First and Last Position (34)

Plain words: given a sorted array with possible duplicates and a target, return the first and last indices of the target as [first, last], or [-1, -1].

Insight: the first index is the lower bound (first ≥ target); the last is (upper bound) − 1 (upper bound = first > target). Two runs of the same template. The implementation below requires integer values and an integer target: target + 1 is the next possible integer. For floats such as [1.0, 1.5], lower(1.0 + 1) - 1 would wrongly include 1.5; use a direct > target predicate or bisect_right for general ordered values.

def searchRange(nums, target):
    def lower(x):                      # first index with nums[i] >= x
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] >= x:
                hi = mid
            else:
                lo = mid + 1
        return lo
    left = lower(target)
    if left == len(nums) or nums[left] != target:
        return [-1, -1]
    right = lower(target + 1) - 1      # (first index > target) - 1
    return [left, right]

Complexity: O(log n) time, O(1) memory. Follow-up — "count occurrences": it's right − left + 1, or lower(target+1) − lower(target) directly.

3. First Bad Version (278)

Plain words: versions 1..n; once a version is bad, all later ones are bad. Given an isBadVersion(v) API, find the first bad version with as few calls as possible.

Insight: the predicate isBadVersion is monotone (False...False, True...True). Here n >= 1 and version n is guaranteed bad: [1, n] is an inclusive answer range with a known-True upper endpoint, rather than an array domain with a possibly absent answer. If no version is bad, this function still returns n; it does not detect that out-of-contract case.

def firstBadVersion(n, isBadVersion):
    lo, hi = 1, n                      # answer in [1, n]
    while lo < hi:
        mid = lo + (hi - lo) // 2      # overflow-safe (the whole point of this problem)
        if isBadVersion(mid):
            hi = mid                   # bad -> boundary is here or left
        else:
            lo = mid + 1               # good -> boundary is strictly right
    return lo

Complexity: O(log n) API calls, O(1) memory. Follow-up — "why lo + (hi − lo)//2?": for 0 <= lo <= hi <= INT_MAX in a fixed-width signed type, lo + hi can overflow but lo + (hi - lo)//2 stays representable. This does not cover arbitrary negative lower endpoints.

Tradeoff

Decision: Choose a binary search formulation to standardise on.

Name: Half-open 'first true' (lo < hi, return lo)

Gain: One template covers search, insert, first/last, and search-on-answer; no 'best so far' variable.

Cost: You must frame each problem as a monotone predicate.

Pick: Default for monotone first-True boundary problems.

Name: Closed interval (lo <= hi, return mid)

Gain: Reads like the textbook; natural for pure exact-match.

Cost: Requires its own invariant and final return rule; do not mix it with the half-open updates.

Pick: Exact-match search, or boundary search when you can state the closed-interval invariant above.

Name: Library bisect (bisect_left/right)

Gain: A tested boundary-search implementation; fewer handwritten loop rules.

Cost: Hidden mechanics; some reviewers want the hand-written version.

Pick: In production and whenever a reviewer allows the standard library.

Verdict: Standardise on the half-open first-True template to reduce memorisation; use bisect where appropriate. A closed formulation is equally valid when its invariant and return rule match.

Where this shows up

The standard-library bisect module exposes these insertion boundaries directly. A sorted index page is another place where a boundary search can locate a key range, provided the page offers ordered random access. A linear good-then-bad sequence of software versions models First Bad Version; a real commit graph, skipped tests, or a bug that disappears and reappears needs more care than that array model.

Checkpoint

You can now…

• Write the half-open 'first true' template from muscle memory.

• State the loop invariant and argue termination and correctness.

• Reframe search, insert-position, and first/last occurrence as one predicate.

• Use bisect_left / bisect_right and know what each returns.

• Explain and use the overflow-safe midpoint lo + (hi − lo)//2.

• Apply the template to a monotone predicate that isn't even an array (First Bad Version).

Quiz

Self-check (answer follows each question).

Recall check

Q: Write the four-line half-open template loop body and its return value.

A: while lo < hi: mid = lo + (hi−lo)//2; if predicate(mid): hi = mid else: lo = mid+1; then return lo.

Q: When predicate(mid) is True, do you set hi = mid or hi = mid − 1, and why?

A: hi = mid — mid itself might be the first True, so you keep it as a candidate; mid − 1 could discard the answer.

Q: Why use lo + (hi − lo) // 2 instead of (lo + hi) // 2?

A: For nonnegative indices within the integer type's maximum, lo + hi may overflow while lo + (hi − lo)//2 stays representable. Python integers are arbitrary precision; arbitrary signed endpoints need a separate overflow analysis.

Q: What does the loop return when the predicate is never true in the range?

A: hi (the exclusive upper bound), i.e. len(array) for a search — the insertion point past the end.

Q: What does bisect_right return and how do you get the last index of a target from it?

A: bisect.bisect_right(nums, target) returns the first index strictly greater than the target; subtract one for the last occurrence, after checking that the target is present.

Q: ★ Stretch: prove the loop terminates.

A: When lo < hi, mid satisfies lo ≤ mid < hi. The True branch sets hi = mid < old hi; the False branch sets lo = mid + 1 > old lo. Either way the interval [lo, hi) strictly shrinks by ≥ 1, so after finitely many steps lo == hi and the loop exits.

Stretch: true

Practice queue

+7d / +21d mark spaced-repetition anchors.

• Binary Search (704) — Easy · the template · +7d anchor.
• Search Insert Position (35) — Easy · lower bound.
• First Bad Version (278) — Easy · predicate over a range.
• Guess Number Higher or Lower (374) — Easy · the guessing game.
• Find First and Last Position (34) — Medium · two boundaries · +21d anchor.
• Sqrt(x) (69) — Easy · binary search on the answer (previews L15).
• Search a 2D Matrix (74) — Medium · flatten to one index space (previews L14).

Corrective source notes

• Binary Search - Algorithms for Competitive Programming — Binary search can find a transition in an arbitrary monotone Boolean predicate. Checked 2026-10-07.

• CPython v3.14.0 bisect documentation — exact left/right insertion partitions and the sorted-input precondition; checked 2026-10-09.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.