Skip to content

017 — Binary Search

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 2 revisions

17 — Binary Search

The last three chapters all walked pointers through data one step at a time — even Fast and Slow Pointers, for all its cleverness, still touches every node. Binary Search is a different kind of move entirely: instead of walking, it cuts the search space in half every single step, by exploiting a structure that's sorted, or "monotonic" in some other sense.

🍽️ Intuition

The Arrays and Strings chapter covered the data structure itself — a contiguous, indexable block of elements where any position is reachable in O(1). This chapter is about recognizing when that indexability lets you skip most of the array entirely: whenever the array (or some derived range) is sorted or monotonic, jumping straight to the midpoint beats walking it step by step.

Picture guessing a stranger's age in a party game where you only get "higher" or "lower" as feedback after each guess. A bad strategy is guessing 1, then 2, then 3 — you'd need up to 99 guesses to nail down an age between 1 and 100. A good strategy is guessing 50 first: whichever way the answer swings, you just eliminated half the remaining possibilities in a single guess. Guess the midpoint of what's left, again and again, and 100 possibilities collapse to the right answer in about 7 guesses, not 99. Doubling the range only costs you one more guess — that's the signature of logarithmic behavior.

The key requirement that makes this work: the feedback has to be monotonic — "higher" always means the true age is strictly above your guess, never sometimes above and sometimes below. Binary Search only works when you can always tell, from one comparison, which entire half to discard.

🚩 Recognition Signal

Binary Search is a strong reach when you see:

  • "Sorted array" combined with "find target", "find the first/last occurrence of", or "find the insertion point" — the textbook case, and the most literal signal.
  • "Minimize the maximum" or "maximize the minimum" phrasing over a range of possible answers — e.g. "minimize the largest sum among k subarrays," "find the smallest capacity that ships all packages within D days." This is binary search on the answer: you're not searching an array at all, you're searching a range of possible answer values, checking at each midpoint guess "is this answer feasible?" via some other function.
  • A rotated sorted array — "search in a rotated sorted array" — still solvable with a modified binary search, because even after rotation, at least one half of any subrange remains properly sorted.
  • "O(log n)" explicitly required, or an input size in the constraints like 10^9 that makes any O(n) scan clearly too slow — a strong hint the intended solution repeatedly halves a search space rather than scanning it.

The unifying tell: there's a monotonic condition — something that's true up to some point and false after (or vice versa) — even if there's no literal sorted array in sight.

📊 ASCII Diagram

Classic binary search for 23 in a sorted array — the search space (shown as [lo...hi]) halves every step:

index:  0   1   2   3   4   5   6   7
array: [2,  5,  8, 12, 16, 23, 38, 56]

step 1: lo=0, hi=7, mid=3 → arr[3]=12 < 23 → discard LEFT half (indices 0-3)
                lo──────hi
        [2,  5,  8, 12 |16, 23, 38, 56]
                         └── search space shrinks to indices 4-7

step 2: lo=4, hi=7, mid=5 → arr[5]=23 == 23 → FOUND at index 5!

Each step eliminates HALF the remaining candidates — 8 elements
became "found" in just 2 comparisons, not 8.

💻 Generic Swift Template

func binarySearchTemplate(_ array: [Int], target: Int) -> Int {
    var lo = 0
    var hi = array.count - 1

    while lo <= hi {
        let mid = lo + (hi - lo) / 2   // avoids overflow vs. (lo + hi) / 2

        // 🔧 Fill in: the condition that decides which half to keep.
        if array[mid] == target {
            return mid                  // 🔧 Found — return/record the answer.
        } else if array[mid] < target {
            lo = mid + 1                 // 🔧 Target's bigger — discard the left half.
        } else {
            hi = mid - 1                 // 🔧 Target's smaller — discard the right half.
        }
    }

    return -1   // 🔧 Not found — lo now marks the insertion point, if that's needed instead.
}

// "Binary search on the answer" shape: same halving, but `isFeasible` replaces array comparison.
func binarySearchOnAnswer(lo initialLo: Int, hi initialHi: Int, isFeasible: (Int) -> Bool) -> Int {
    var lo = initialLo
    var hi = initialHi

    while lo < hi {
        let mid = lo + (hi - lo) / 2
        if isFeasible(mid) {
            hi = mid          // 🔧 mid works — it might be the best answer, keep it in range.
        } else {
            lo = mid + 1       // 🔧 mid fails — the answer must be strictly bigger.
        }
    }

    return lo   // lo == hi: the smallest value for which isFeasible returns true.
}

The skeleton never changes: shrink a [lo, hi] range by evaluating the midpoint and discarding the half that can't contain the answer, repeat until the range collapses to zero or one candidate. What differs per-problem is the comparison at the midpoint — a direct array lookup for classic search, or a call to a problem-specific isFeasible function for binary-search-on-the-answer.

🧩 Worked Example

Koko Eating Bananas — Koko has piles of bananas and h hours to eat them all. Each hour she picks one pile and eats up to speed bananas from it (if the pile has fewer, she finishes it and stops for that hour). Find the minimum integer speed such that she finishes all piles within h hours.

func minEatingSpeed(_ piles: [Int], _ h: Int) -> Int {
    func hoursNeeded(atSpeed speed: Int) -> Int {
        // Ceiling division per pile: eating 10 bananas at speed 3 takes 4 hours, not 3.
        piles.reduce(0) { $0 + ($1 + speed - 1) / speed }
    }

    var lo = 1                    // slowest conceivable speed
    var hi = piles.max() ?? 1     // fastest speed that's ever necessary — finishes any single pile in 1 hour

    while lo < hi {
        let mid = lo + (hi - lo) / 2
        if hoursNeeded(atSpeed: mid) <= h {
            hi = mid              // mid is fast enough — try to go even slower
        } else {
            lo = mid + 1           // mid is too slow — need more speed
        }
    }

    return lo
}

// smoke test
print(minEatingSpeed([3, 6, 7, 11], 8))   // 4
print(minEatingSpeed([30, 11, 23, 4, 20], 5))   // 30

Mapped onto binarySearchOnAnswer: the search space isn't the piles array at all — it's the range of possible speeds, from 1 to piles.max(). isFeasible(mid) is hoursNeeded(atSpeed: mid) <= h — "can Koko finish in time at this speed?" That feasibility is monotonic (any speed faster than a working speed also works), which is exactly the property Binary Search requires. The halving logic is copied verbatim from the template; only the feasibility check is new.

🧸 Memory Sentence

Binary Search is the "higher or lower" guessing game — every guess at the midpoint throws away half of what's left, turning millions of possibilities into a couple dozen guesses.

✅ Check Your Understanding

A problem says: "You're given a mountain array (strictly increasing then strictly decreasing) — find the peak element's index." Is this array sorted in the traditional sense? Explain why Binary Search still applies here, and describe what comparison at mid tells you which half to discard.

⬅️ Previous: Fast and Slow Pointers · Next: DFS and Backtracking ➡️

Clone this wiki locally