Binary Search — the Pattern Behind 100 Problems

Review boundary and corrected contracts

Predicate monotonicity, feasible upper bound and shrinking range are the proof obligations. The floating bisection is a fixed-iteration approximation, not an exact real root. Negative square-root input now raises; shipping expects positive weights/days.

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.

Learning objective: Write two bulletproof binary-search templates and recognise the pattern in problems that don't look like binary search.

Why this session exists

Binary search discards a provably irrelevant part of an ordered search space at each step. Exact lookup is one use; finding the first feasible capacity is another. Both require a precise boundary contract and a progress argument. This session develops those contracts, then tests them on duplicates, missing values and an answer-space problem.

You will be able to

• Write the classic and lower-bound templates from memory, and explain why the loop conditions differ.

• Spot the ‘hidden’ binary search inside problems phrased as ‘minimum X such that predicate(X) is true’.

• Use Python's bisect module in real code instead of hand-rolling loops.

• Explain the Josh Bloch overflow bug and when mid = lo + (hi - lo) // 2 avoids fixed-width overflow.

• Debug the two failure modes: infinite loop (lo never moves) and off-by-one (miss the answer by 1).

Prerequisites

• S023 — Arrays & Lists — the Everyday Container — you need O(1) random access for O(log n) to matter.
• S027 — Recursion — Call Stack, Base Case — a recursive binary-search variant appears in the exercise.

Pre-read · skim before the session (25 min total)

Further reading: Python bisect — Array bisection algorithm

Further reading: Binary Search on Real Numbers and Predicates

Further reading: Nearly All Binary Searches and Mergesorts Are Broken

(a) Intuition · 5 min

Guess the number between 1 and 1000

Real: A friend picks a number between 1 and 1000; you guess; they say higher or lower. Nobody guesses 1, 2, 3 — you guess 500, then 250 or 750, then 125 or 375, halving the range every turn. Ten guesses is enough because 2¹⁰ = 1024 > 1000. Twenty guesses covers a million. Thirty covers a billion. You could find a single row among the entire US population in the same number of guesses it takes to make a cup of coffee.

 
    Binary search is that game, written down: keep two pointers lo and hi, look at the middle, throw away the half that cannot contain the answer, repeat. Each iteration shrinks the search space by about half. Classic search takes at most floor(log₂ n) + 1 midpoint probes for n > 0, and none for an empty array; total work is O(log(n + 1)) with O(1) access/comparisons.
    The one hard prerequisite is monotonicity: the data must be sorted, or, more generally, the answer to the question "is X the answer or too small?" must consist of a False prefix followed by a True suffix; either part may be empty.
  

The three shapes binary search takes in the wild

• Classic search — find target in a sorted array. Returns index or -1. Loop condition: lo <= hi.

• Lower / upper bound — first index with value ≥ target / > target, respectively. Both return an insertion point, possibly n. Loop condition: lo < hi.

• Binary search on the answer — the array is imaginary; you search over a range of possible answers \[lo, hi] and evaluate a monotonic predicate feasible(x) at each mid. Same halving, no array.

Two failure modes, both silent

Two common boundary bugs are:

ClassName: ml-4 list-decimal

Infinite loop — the update doesn't shrink the space. Usually lo = mid with an even-length window: mid == lo, so lo never moves. Off-by-one — the answer is at index k but you return k-1 or k+1. Usually a loop-condition mismatch (< vs <=).

Use a consistent template, write its invariant, and test empty, singleton, duplicate and absent-target cases. Memorization alone does not prove a changed predicate correct.

(b) Shrinking a search without losing the answer · 15 min

The historical bugs show why both boundary conventions and midpoint arithmetic are part of correctness, not implementation trivia. Start with an exact lookup, then change the question to finding the first feasible answer.

Classic search for 23 in a 10-element sorted array

At each arrow, check both claims: 23 is still inside the surviving interval, and that interval is strictly smaller. The tested midpoint can be discarded when it is not the target.

Three midpoint probes for this 10-element example. For a million elements the same loop needs at most 20 probes (each may perform more than one Python comparison). That's the whole point.

Notice that both failed comparisons move past the midpoint. A lower-bound search cannot always do that: a midpoint satisfying the predicate may itself be the first valid answer. This is why the two templates below have different boundary updates.

The two templates — memorise these, do not improvise

Name: Template A · classic

Tagline: Return index or -1

• Space: \[lo, hi] — both ends inclusive

• Init: lo=0, hi=n-1

• Loop: while lo <= hi:

• Miss right: lo = mid + 1

• Miss left: hi = mid - 1

• Exit: return -1

Name: Template B · lower bound

Tagline: Return first index where predicate True

• Space: \[lo, hi) — hi is exclusive

• Init: lo=0, hi=n (NOT n-1)

• Loop: while lo < hi:

• Predicate False at mid: lo = mid + 1

• Predicate True at mid: hi = mid

• Exit: return lo (== hi)

The five-step walk you can execute on any binary-search problem

1. Define the search space

Desc: What is lo and hi? An array index? A day count? A capacity in kg? A floating-point rate?

2. State the predicate

Desc: A Boolean function with a False prefix and True suffix, allowing all-False or all-True. Specify the return convention when no satisfying value exists.

3. Pick a template

Desc: Classic (Template A) for value lookup, lower-bound (Template B) for ‘smallest X such that predicate’.

4. Write the loop

Desc: Compute mid with arithmetic valid for your bound types, evaluate the predicate, and update the bounds without discarding a possible boundary.

5. Prove termination

Desc: Each iteration must strictly shrink hi - lo. If not → infinite loop.

Binary search on the answer — the pattern that makes seniors

Problem: ship packages within D=5 days on a boat with capacity C. Weights = [1..10]. Find the smallest C that works.

Here a larger capacity cannot make a feasible shipment infeasible. Follow how each successful test keeps the tested capacity as a possible minimum, while a failed test rules it out along with every smaller capacity.

No sorted array in sight. The search space is [10, 55], and the predicate feasible(C) is monotonic: once true, it stays true. This run tests capacities 32, 21, 15, 12 and 14, using five predicate evaluations.

Capacity 14 needs six days: [1,2,3,4], [5,6], [7], [8], [9], [10]. Capacity 15 needs five: [1,2,3,4,5], [6,7], [8], [9], [10]. These two adjacent capacities establish the boundary at 15. With the update rules settled, the remaining implementation hazard is how the midpoint itself is calculated.

Overflow, and why Python is a special case

Why mid = (lo + hi) // 2 is a landmine in most languages

Name: Fixed-width integers — language rules differ

Desc: Java int is signed 32-bit and overflowing addition wraps. C and C++ signed overflow is undefined behavior, not a portable negative result. Go int is implementation-sized (32 or 64 bits) and its signed overflow is defined. Josh Bloch's historical Java example illustrates why a mathematically correct average can still be an invalid machine computation.

Name: The safe form · mid = lo + (hi - lo) // 2

Desc: For representable nonnegative bounds 0 ≤ lo ≤ hi ≤ MAX, the difference and final midpoint fit the signed type. Arbitrary signed ranges can still overflow in hi − lo; use a suitable wider type or a language-provided midpoint routine. Java's unsigned-shift idiom has its own nonnegative-bound contract; no speed claim is needed.

Name: Python — arbitrary precision int

Desc: Python int grows as needed, so these integer formulas avoid fixed-width overflow, subject to available memory. NumPy fixed-width integer scalars and floats have different behavior; translating code still requires checking the target type and bounds.

Overflow is only one way a plausible-looking loop can fail. Duplicates expose a different ambiguity: returning an equal element is not the same task as returning the first equal element.

Myth: "Binary search is easy — I understood it in five minutes. It's the simplest algorithm there is."

Truth: The idea is trivial; the implementation is famously not. Off-by-one errors in the boundary update, the wrong loop condition, and integer overflow in (lo+hi)/2 are all classic bugs — the overflow one sat undetected in widely used library code for years. Exact lookup and boundary lookup solve different tasks; choose rather than assuming one variant covers both.

Why: Because you learned it on the one variant where the invariants are forgiving: distinct values, target present, return on exact match. Many practical uses are boundary queries on data with duplicates—first occurrence, last occurrence or insertion point. Their strictness and update rules differ. Get that wrong and you get an infinite loop or a silently off-by-one answer, not an exception.

Test: With duplicates, "found it" is ambiguous — and the standard library already solves the variant you need:import bisect xs = [1, 2, 2, 2, 3, 5]

print(bisect.bisect_left(xs, 2)) # 1 - first index where 2 could go print(bisect.bisect_right(xs, 2)) # 4 - one past the last 2 print(bisect.bisect_right(xs, 2) - bisect.bisect_left(xs, 2)) # 3 - count of 2s

# insertion point for a value that is absent print(bisect.bisect_left(xs, 4)) # 5 - after 3 and before 5

# 'return mid on match' returns an equal index, but does not promise the first or last

Question: Why must the array be sorted? The usual answer is "so you know which half to discard" — true but shallow. What is the actual property being exploited?

Premise: Binary search discards half the search space after a single comparison against one element.

Because: a constant-fraction reduction at every step is sufficient for a logarithmic number of probes

Premise: Discarding a half is only valid if one comparison lets you conclude something about every element in that half, not just the one you tested.

Because: you never examine those elements; the conclusion must be inferred, not observed

Premise: That inference requires a monotonic predicate: some yes/no test that is false for a prefix of the array and true for the whole suffix, with at most one False-to-True transition (either region may be empty).

Because: a True test rules out later positions as an earlier boundary; a False test rules out that position and its prefix

Premise: Sortedness is simply the most common way to manufacture such a predicate — for sorted data, "is a[i] ≥ x?" is exactly false-then-true.

Because: sorting makes the comparison to a fixed target monotonic in the index

Conclusion: Therefore the real requirement is not sortedness — it is a monotonic predicate over the search space. Sortedness is one instance of it.And note what this predicts: you can binary search over things that are not arrays at all. Search over an answer space whenever "is answer k feasible?" is monotone — minimum ship capacity under an order-preserving schedule, or minimum machine count under a stated scheduling model. Prove monotonicity for that model; noisy measured latency need not be monotone. With R candidates and predicate cost T, search work is O(T log(R + 1)), not automatically O(log R) total. That reframing — binary search the answer, not the data — is the single highest-value thing in this session.

Name: Shrinking window with an invariant

Picture: For lower bound, unclassified array elements lie in [lo, hi), but the boundary itself lies in the closed interval [lo, hi]. Everything before lo fails the predicate; everything at or after hi within the array satisfies it. If all elements fail, the boundary is the sentinel n. Testing mid classifies a region and preserves that promise until lo == hi. This distinction explains why assigning hi = mid retains mid as a possible answer even though it leaves the unclassified half-open interval.

• State the invariant explicitly: "everything left of lo fails the predicate, everything at or right of hi satisfies it." Then the loop body writes itself.

• The window must shrink strictly every iteration. If lo = mid is possible, you can loop forever — that is why it is usually lo = mid + 1.

• Check arithmetic separately: with nonnegative representable fixed-width bounds, lo + (hi − lo) // 2 avoids the overflowing sum. Python int does not have that fixed-width limitation.

• Prefer bisect_left / bisect_right over hand-rolling. Hand-roll only when searching an answer space rather than an array.

Trigger: Fire this model the moment you see: a sorted array or index · "first/last occurrence" · "insertion point" · a range query on a time-ordered dataset · Parquet row-group or file min/max pruning · a database index seek · and any optimisation phrased as "smallest X such that Y holds" where Y is monotone in X.

Decision: You have a large collection and need repeated lookups. Sort it and binary search, or hash it?

Name: Sorted array + binary search

Gain: O(log n) probes with random access; supports boundary, predecessor and range queries. Storage depends on representation, and binary-search probes are not a sequential scan. Fixed-width records can support direct offsets in a sorted file; variable-width formats need indexing

Cost: comparison sorting costs O(n log n) in the general case; array insertion can shift O(n) entries. Mutability is possible but may be expensive under frequent inserts

Pick: static or bulk-rebuilt data and ordered queries. LSM sorted runs are a relevant use; columnar storage alone does not imply sorted rows

Name: Hash map

Gain: expected O(1) lookup and amortised insertion under ordinary hashing assumptions. Actual constants, key costs and collision behavior decide whether it wins

Cost: no efficient key-sorted range query from the hash index alone, extra table capacity, and O(n) worst-case lookup. Python dicts do preserve insertion order; that is not key order. Memory ratios and disk layouts are implementation-specific

Pick: lookups are exact-match only and the collection changes — caches, joins, dedup sets

Name: Linear scan

Gain: no auxiliary index, works on unsorted/unhashable values, and can be competitive for small inputs or few queries. A Python list scan is not automatically vectorized or branch-free

Cost: O(n) worst-case per lookup, hence O(mn) for m queries; quadratic specifically when m grows proportionally to n

Pick: small inputs or few queries where indexing cost is not amortized; measure rather than imposing a universal query-count cutoff

Verdict: Sorting can make boundary queries and selective storage reads efficient, but min/max pruning is not itself synonymous with binary search. Parquet's page-index specification distinguishes ordered page bounds, which permit binary search, from unordered bounds, which a reader can scan. How many blocks can be skipped depends on data clustering, statistics, predicates and reader support—not a universal percentage.

(c) Hands-on · 25 min

Save as bsearch_lab.py, run with python3 bsearch_lab.py. Every function is annotated; each print shows a concrete result. Array examples require ascending order and a consistent total ordering. Shipping requires a nonempty reusable sequence of positive integer weights and a positive integer day count; the toy function does not validate that contract. The float exercise is intended for finite moderate nonnegative inputs, not a production root solver.

"""bsearch_lab.py — three shapes of binary search, one file."""
from __future__ import annotations
import bisect
import math
from typing import Callable, List
 
# ---------- Template A · classic ----------
def binary_search(arr: List[int], target: int) -> int:
    """Return index of target, or -1. Space: [lo, hi]."""
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2        # overflow-safe form
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1                 # target is strictly right
        else:
            hi = mid - 1                 # target is strictly left
    return -1
 
# ---------- Template B · lower bound ----------
def lower_bound(arr: List[int], target: int) -> int:
    """First index i where arr[i] >= target. == bisect_left. Space: [lo, hi)."""
    lo, hi = 0, len(arr)                 # note: hi = n, not n-1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1                 # predicate (>= target) still False
        else:
            hi = mid                     # predicate True, but earlier index may also be True
    return lo
 
def upper_bound(arr: List[int], target: int) -> int:
    """First index i where arr[i] > target. == bisect_right."""
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo
 
# ---------- Binary search on the answer ----------
def min_ship_capacity(weights: List[int], days: int) -> int:
    """Smallest capacity C such that all weights ship in <= days days, in order."""
    def feasible(cap: int) -> bool:
        d, load = 1, 0
        for w in weights:
            if load + w > cap:
                d += 1
                load = 0
            load += w
        return d <= days
 
    lo, hi = max(weights), sum(weights)  # search space
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid                     # try smaller
        else:
            lo = mid + 1                 # need bigger
    return lo
 
def bsearch_float(predicate: Callable[[float], bool],
                  lo: float, hi: float,
                  iterations: int = 100) -> float:
    """Fixed-iteration float binary search — safer than epsilon comparisons."""
    for _ in range(iterations):
        mid = (lo + hi) / 2
        if predicate(mid):
            hi = mid
        else:
            lo = mid
    return lo
 
def sqrt(n: float) -> float:
    """Compute sqrt via binary search on the answer."""
    if n < 0:
        raise ValueError("real square root needs nonnegative n")
    return bsearch_float(lambda x: x * x >= n, 0.0, max(1.0, n))
 
# ---------- Demo ----------
if __name__ == "__main__":
    arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
    print("classic search(23):    ", binary_search(arr, 23))     # 5
    print("classic search(24):    ", binary_search(arr, 24))     # -1
    print("lower_bound(24):       ", lower_bound(arr, 24))       # 6
    print("upper_bound(23):       ", upper_bound(arr, 23))       # 6
    print("bisect.bisect_left(24):", bisect.bisect_left(arr, 24))
 
    dupes = [1, 2, 2, 2, 3]
    print("count of 2 via bounds: ", upper_bound(dupes, 2) - lower_bound(dupes, 2))  # 3
 
    weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    print("min capacity (5 days): ", min_ship_capacity(weights, 5))   # 15
    print("min capacity (3 days): ", min_ship_capacity(weights, 3))   # 21
 
    print(f"sqrt(2) ≈ {sqrt(2):.10f}  vs math.sqrt = {math.sqrt(2):.10f}")

Anatomy of the script

Name: from \_\_future\_\_ import annotations

Desc: Postpones evaluation of annotations in the runtimes used here. typing.List[int] already predates Python 3.9; this import is not what enables it. Annotation syntax support and runtime behavior should be checked separately.

Name: mid = lo + (hi - lo) // 2

Desc: A midpoint formula safe for nonnegative representable fixed-width bounds. Python int can use either formula; translating it requires the target language's integer contract.

Name: Template A vs B: hi=n-1 vs hi=n

Desc: One character, entirely different semantics. Template A searches inside the array; Template B searches for an insertion point (which can be past the end).

Name: bisect.bisect\_left

Desc: The standard boundary-search API; CPython normally supplies a C accelerator. It uses ordering, not equality, and assumes the sequence remains sorted and is not concurrently mutated. Use custom search when the predicate or access model differs.

Name: min\_ship\_capacity's feasible()

Desc: Each predicate evaluation scans n weights. With S = sum(weights) − max(weights), total work is O(n(1 + log(S + 1))), including computing the initial bounds. The +1 terms cover the singleton search range S=0.

Name: bsearch\_float(..., iterations=100)

Desc: Fixed iteration count instead of while hi - lo > eps. Prevents infinite loops when eps is smaller than the machine epsilon at hi's magnitude.

What to observe when you run it

ClassName: ml-4 list-decimal space-y-1

lower_bound(24) == 6: the array has 6 items ≤ 23; 24 would go at index 6 (past 23 at index 5). upper_bound(23) - lower_bound(23) would be 1 (one copy of 23). The dupes example shows this generalises: three 2's → difference 3. For five days, min_ship_capacity calls feasible five times while narrowing [10,55]. The float sqrt is a bounded approximation, not a universal full-precision routine. In exact arithmetic 100 halvings reduce the initial interval width by 2¹⁰⁰; the absolute error still depends on that initial width. Very large inputs can overflow x*x, very small inputs can remain unresolved, and floating-point bounds can stagnate. Use math.sqrt for ordinary numerical work.

Goal: Break the templates deliberately to see the two failure modes

Hint: Try each break in isolation. Undo before trying the next.

Do these three edits, one at a time, and observe:

# Break 1 — Template A with `lo < hi` instead of `lo <= hi`
# Symptom: binary_search(arr, arr[-1]) returns -1 for the last element.
 
# Break 2 — Template B with `hi = mid - 1` instead of `hi = mid`
# Symptom: `lower_bound([1,2,3,4,5], 3)` returns 1 instead of 2 (off-by-one).
 
# Break 3 — In min_ship_capacity, replace `lo = mid + 1` with `lo = mid`
# Symptom: infinite loop when `feasible(mid) == False` and `mid == lo`.
# Kill with Ctrl-C after ~1 second.

After restoring the correct updates, test all boundary cases again. Keep a bounded step counter in a test harness when examining an intentionally nonterminating mutant.

(d) Production reality · 15 min

Where this shows up in the rest of the plan

Root: Binary search sits underneath a surprising amount of the series

Label: S033 · Dynamic Programming

Desc: Some DPs (e.g. LIS in O(n log n)) use binary search to place elements into patience piles.

Label: S037 · SQL Joins

Desc: A conventional sort-merge join advances pointers through sorted inputs; it does not require binary search. Lower bounds can help with particular indexed or batched lookup variants.

Label: S041 · Indexes — B-Tree

Desc: B-tree nodes keep ordered separator keys. Searching within a node may use binary search or another strategy; node layout and fanout determine the implementation.

Label: S048 · Data serialization

Desc: Min/max statistics can exclude blocks that cannot satisfy a predicate. Binary search requires ordered searchable metadata; arbitrary block pruning may simply scan bounds.

Label: S056 · Docker

Desc: git bisect on a Dockerfile change history is a real production skill.

Label: S090 · System design — search

Desc: Sharded search over sorted document IDs starts with a binary search on the shard boundaries.

The senior engineer tell

Ask whether the predicate is monotone, identify the candidate interval, and define the no-solution result before choosing a template. Use bisect for ordered in-memory sequences; write and test a custom loop for an answer-space predicate.

(e) Recall + stretch · 10 min

Self-check (answer follows each question).

Q: How many comparisons does binary search need on 1 billion sorted elements, worst case?

A: At most 30 midpoint probes for classic search on one billion elements, since floor(log₂ n) + 1 = 30. The shown code may do both equality and ordering comparisons at one probe; 30 is not the exact count of Python comparison operations.

Q: Why is mid = lo + (hi - lo) // 2 preferred over mid = (lo + hi) // 2?

A: With 0 ≤ lo ≤ hi ≤ MAX, the difference formula avoids a possibly overflowing sum and keeps the result within bounds. Java wrapping, C/C++ undefined signed overflow and Go's defined overflow are distinct. Negative bounds may invalidate the difference argument. Python int is arbitrary precision, while fixed-width library scalar types may still overflow.

Q: What does bisect.bisect\_left(arr, x) return for arr = \[1, 2, 2, 2, 3] and x = 2 versus x = 4?

A: For x=2: index 1 (the first position where 2 could go while keeping order). For x=4: index 5 (past the end of a 5-element array — this is why the search space upper bound is n, not n-1).

Q: Give one problem that isn't ‘find a value in a sorted list’ but is still solved by binary search.

A: ‘Smallest ship capacity C such that packages ship in D days’ (LeetCode 1011 / Capacity To Ship Packages). Or ‘median of two sorted arrays’ (binary search on partition indices). Or ‘git bisect’ (binary search on commit history). Or ‘square root via bisection on a bracket’. Newton's method is a different update rule. All share: a monotonic predicate on a searchable range.

Q: You wrote a binary search on 100 elements; it runs forever. Name two likely bugs.

A: (1) The update doesn't shrink the space — e.g. lo = mid when the predicate is False and mid == lo. (2) You update the wrong bound, so the interval repeats or expands. It is not necessary for both bounds to move in every run; it is necessary for the integer search measure to decrease on every non-returning iteration.

Q: What is the time complexity of min\_ship\_capacity(weights, days)?

A: O(n(1 + log(S + 1))), where n = len(weights) and S = sum(weights) − max(weights), counting integer operations at unit cost. Computing the bounds costs O(n); each predicate evaluation also scans the weights. This includes S=0, when no search iteration is needed.

Q: When you binary-search on floats, why is while hi - lo > eps dangerous, and what's the safer form?

A: Rounding can make the midpoint equal an endpoint, so the interval stops shrinking even while hi − lo exceeds eps. A fixed iteration cap guarantees termination, not a requested accuracy. In exact arithmetic the final interval width is the initial width divided by 2¹⁰⁰; floating-point rounding and predicate overflow can prevent that bound. Check numerical error separately.

Q: You must binary-search a linked list of 1M nodes. What's the time complexity, and why?

A: O(n) traversal work is achievable if each midpoint is found by walking within the current retained sublist: the scanned lengths form a geometric series. A naive implementation that restarts at the original head for every absolute midpoint can instead take O(n log n) traversal work. Neither gives array-like O(log n) time; choose an array, skip list or search tree if repeated ordered lookups justify it.

Q: In Template B, why do we write hi = mid instead of hi = mid - 1?

A: Because Template B searches for the first index where the predicate is True. When predicate(mid) is True, mid is a valid boundary candidate. Setting hi = mid removes it from the unclassified element interval [lo, hi) but retains it in the closed candidate interval [lo, hi]. Setting hi = mid − 1 can drop that candidate.

Q: Stretch — Implement search\_rotated(arr, target) for a strictly increasing array rotated at an unknown pivot (e.g. \[4,5,6,7,0,1,2], target=0 → index 4). Time must be O(log n).

Stretch: true

A: At each step, one of the two halves [lo..mid] or [mid..hi] is fully sorted (you can tell by comparing arr[lo] and arr[mid]). Check whether target lies inside that sorted half; if yes, recurse there; if no, recurse in the other half. Same O(log n), one extra branch per step. This assumes distinct values. With duplicates, equal endpoints can hide which half is ordered and the worst case can degrade to O(n).

Explain-out-loud test

1. What is binary search? (one sentence, no code)
2. What is the one prerequisite the input must satisfy? (and give one non-array example)
3. Why do senior engineers reach for bisect_left instead of writing the loop? (one sentence)

Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: intuition → visual → hands-on → production war stories → recall. Duration: 90 minutes.

Grind this pattern in the LeetCode track

This session builds the mental model for binary search. The full pattern treatment — templates, five graded problems each, and the design review follow-ups — lives in the dedicated LeetCode series:

L13 · Binary Search I · L14 · Binary Search II · L15 · Binary Search III

Do the concept here, then go there to build the reflex.

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.

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.