S032 · Binary Search — the Pattern Behind 100 Problems

Module M03: Data Structures & Algorithms · Session 32 of 130 · Track: SW 🎯

What you'll be able to do after this session

• Explain Binary Search to a friend in one minute, out loud, no notes.
• Recognise it when you see it in real code / systems / papers.
• Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

• S023 — Arrays & Lists — the Everyday Container

Pre-read (skim before the session)

• 🎥 Intuition (5–15 min) · Binary Search in 100 Seconds — Fireship — the fastest intro; nails the halving idea.
• 🎥 Deep dive (30–60 min) · NeetCode — Binary Search Playlist Intro — walks through off-by-one bugs and the "search space" mindset.
• 🎥 Hands-on demo (10–20 min) · Errichto — Binary Search on the Answer — shows the hidden pattern behind "min/max feasible value" problems.
• 📖 Canonical article · Python bisect module docs — the standard-library binary-search primitives you'll actually use.
• 📖 Book chapter / tutorial · CP-Algorithms — Binary Search — canonical treatment including "binary search on real numbers" and predicate framing.
• 📖 Engineering blog · Google Research — "Nearly All Binary Searches Are Broken" — Joshua Bloch's famous integer-overflow bug in java.util.Arrays.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: Sorted + bisect = O(log n).

Think of guessing a number between 1 and 1000 where a friend answers "higher" or "lower." Nobody sensible guesses 1, 2, 3… — you guess 500, then 250 or 750, halving the range every turn. After 10 guesses you've narrowed 1000 options to 1. That's binary search, and it's the reason log₂(1_000_000_000) ≈ 30 — you can find one row among a billion in 30 comparisons.

The whole trick has one hard prerequisite: the data must be sorted (or, more generally, have a monotonic property — something that flips from False to True exactly once as you scan). Once that's true, you keep two pointers lo and hi, look at the middle, and throw away the half that can't contain the answer.

Binary search shows up disguised. "Find the smallest x such that can_ship_in_x_days(x) == True" is binary search over a range of days. "Find the k-th smallest element in two sorted arrays" is binary search on partition indices. Once you see the shape, you see it everywhere.

The forever gotcha: the loop condition (while lo < hi vs <=) and the update (hi = mid vs mid - 1) must agree with your definition of the search space, or you'll get infinite loops or off-by-ones. Pick one template and stick with it.

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

Search for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (10 elements, indices 0–9):

Three comparisons for 10 elements. For 1 million elements the same loop needs ≤ 20 comparisons.

Template you should memorise — the "search-space shrink" form:

Second worked example — "binary search on the answer." Problem: you must ship packages within D=5 days on a boat with capacity C. Package weights = [1,2,3,4,5,6,7,8,9,10]. Find the smallest capacity C that works.

• C=15 → days = 4 (works). C=14 → 4 (works). C=13 → 4 (works). C=10 → 6 (fails).
• Binary-search C between max(weights)=10 and sum(weights)=55.

Same halving pattern, no sorted array in sight — the search space is [10..55] and the predicate feasible(C) is monotonic (once it turns True, it stays True).

The famous overflow bug (Josh Bloch's blog): mid = (lo + hi) / 2 overflows a 32-bit int when lo + hi > 2³¹. Correct form: mid = lo + (hi - lo) // 2. Python's ints are unbounded so you're safe — but any Java / C / Go binary search must use this form.

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

Save as bsearch_lab.py and run with python3 bsearch_lab.py:

import bisect
import math
 
def binary_search(arr, target):
    """Classic: return index of target, or -1."""
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2   # overflow-safe form
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
 
def lower_bound(arr, target):
    """First index i where arr[i] >= target (= bisect_left)."""
    lo, hi = 0, len(arr)            # note: hi = n, not n-1
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo
 
def min_ship_capacity(weights, days):
    """Binary search on the answer: smallest capacity that ships in `days`."""
    def feasible(cap):
        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)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo
 
if __name__ == "__main__":
    arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
    print("index of 23:", binary_search(arr, 23))     # 5
    print("index of 24:", binary_search(arr, 24))     # -1
    print("lower_bound of 24:", lower_bound(arr, 24)) # 6 (insertion point)
    print("stdlib bisect_left(24):", bisect.bisect_left(arr, 24))
 
    weights = [1,2,3,4,5,6,7,8,9,10]
    print("min ship capacity (5 days):", min_ship_capacity(weights, 5))  # 15
    print("min ship capacity (3 days):", min_ship_capacity(weights, 3))  # 20+
 
    # Binary search on floats: sqrt without math.sqrt
    def sqrt(n, eps=1e-9):
        lo, hi = 0.0, max(1.0, n)
        while hi - lo > eps:
            mid = (lo + hi) / 2
            if mid * mid < n: lo = mid
            else: hi = mid
        return lo
    print("sqrt(2) ≈", sqrt(2), "vs", math.sqrt(2))

Checklist — observe when you run:

1. binary_search returns -1 for missing values; lower_bound returns the insertion point — that difference matters for range queries.
2. bisect.bisect_left matches your lower_bound — always prefer the stdlib in real code.
3. min_ship_capacity never enumerates all capacities from 10 to 55 — it evaluates feasible only ~log₂(45) ≈ 6 times.
4. The float sqrt converges to math.sqrt within eps in ~30 iterations regardless of n.
5. Change lo <= hi to lo < hi in binary_search — one test now fails. That's why templates matter.

Try this modification: write upper_bound(arr, target) — the first index i where arr[i] > target. Verify upper_bound - lower_bound == count of target in arr.

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

Binary search is quietly everywhere. Every B-tree lookup in Postgres, every git bisect to find the commit that broke prod, every SSTable seek in Cassandra / RocksDB, every Array.prototype.indexOf on a sorted-lookup table — same pattern.

War story — Josh Bloch, Sun Microsystems, 2006. The java.util.Arrays.binarySearch in the JDK had a bug that survived nine years and multiple code reviews: int mid = (low + high) / 2 overflows when low + high > Integer.MAX_VALUE. It never triggered because arrays over 2 billion were rare — until they weren't. The fix (int mid = (low + high) >>> 1 or low + (high - low)/2) is now taught in every algorithms class specifically because of that bug. Read the Google Research blog post; it's a 3-minute humility pill.

War story — git bisect at Microsoft. A single regression in Windows shell startup cost 200ms across a code base with 40,000 commits between the last known-good and known-bad build. Linear check = 40,000 boots ≈ 3 months. git bisect run <script> did it in log₂(40_000) ≈ 16 boots ≈ 40 minutes. That's the whole value proposition of binary search made corporate.

Common bugs & how good teams avoid them:

• Off-by-one infinite loop. Forgetting mid + 1 when the target is in the right half → lo never advances. Fix: pick one template (the "predicate + while lo < hi + hi = mid / lo = mid + 1" form is bulletproof) and never write raw binary search from scratch again.
• Searching an unsorted array. Sounds obvious but happens when a downstream service silently drops the ORDER BY. Add an assert arr == sorted(arr) in dev; remove in prod.
• Duplicates. Plain binary_search returns any matching index. If you need the first or last, use bisect_left / bisect_right.
• Floating-point predicates. "Binary search on the answer" with floats can oscillate. Use a fixed iteration count (e.g., 100) instead of while hi - lo > eps, which can loop forever near the machine epsilon.

The senior-engineer tell: they reach for bisect_left reflexively instead of writing the loop, and they draw the search space ([lo, hi) vs [lo, hi]) on the whiteboard before writing code.

(e) Quiz + exercise · 10 min

1. What's the maximum number of comparisons binary search makes on 1 billion sorted elements?
2. Why is mid = lo + (hi - lo) // 2 preferred over mid = (lo + hi) // 2?
3. Given arr = [1,2,2,2,3], what does bisect_left(arr, 2) return vs bisect_right(arr, 2)?
4. Describe one real problem that isn't "find a value in a sorted list" but is still solved by binary search.
5. Your binary search on 100 items runs forever. Name two bugs that could cause an infinite loop.
6. Stretch (connects to S023 Arrays): Python lists have O(1) random access — that's why binary search is O(log n) on them. What happens to binary-search complexity if you try it on a linked list, and why?

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

1. What is Binary Search? (one sentence, no jargon)
2. When would you use it? (one concrete example)
3. When would you NOT use it? (one anti-pattern)

What comes next

• Next session (S033): Dynamic Programming — Memoisation & Tabulation
• Previous (S031): Sorting — Merge, Quick, and When to Trust the Built-in
• Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.