Binary Search Patterns: The Template, Boundaries, and 'Search on the Answer'

In plain words

Imagine a game of 'guess the number' between 1 and 1,000. Your opponent says 'higher' or 'lower' after each guess. A smart player immediately guesses 500 — if the answer is lower, the top half is gone; if higher, the bottom half is gone. Then guess the middle of what remains. After ten guesses, the answer is nailed down (2¹⁰ = 1,024 > 1,000). That halving is binary search. The game only works because the search space is ordered — 'higher/lower' carries information. On a shuffled list the answer gives you nothing useful, so halving doesn't help.

Binary search is the payoff for all that sorting. On a sorted array, you never scan linearly: check the middle, and because the data is ordered, one comparison eliminates *half* the remaining elements. Repeat, and a million elements collapse to about twenty checks (log₂(1,000,000) ≈ 20). The idea is simple; the *implementation* is a legendary source of off-by-one and infinite-loop bugs. This lesson gives you a template that resists them and then shows how the pattern reaches far beyond 'find x in an array'.

Array (sorted): [ 1,  3,  5,  7,  9, 11, 13, 15, 17, 19 ]
Indices:           0   1   2   3   4   5   6   7   8   9
Target: 13

Step 1  lo=0, hi=9  → mid=4  → array[4]=9  < 13  → lo = mid+1 = 5
        [ _,  _,  _,  _,  _,  11, 13, 15, 17, 19 ]
                                ↑lo              ↑hi

Step 2  lo=5, hi=9  → mid=7  → array[7]=15 > 13  → hi = mid-1 = 6
        [ _,  _,  _,  _,  _,  11, 13, 15,  _,  _ ]
                                ↑lo  ↑hi

Step 3  lo=5, hi=6  → mid=5  → array[5]=11 < 13  → lo = mid+1 = 6
        [ _,  _,  _,  _,  _,   _, 13,  _,  _,  _ ]
                                    ↑lo=hi

Step 4  lo=6, hi=6  → mid=6  → array[6]=13 == 13  → FOUND at index 6  ✓

Total comparisons: 4  (≈ log₂ 10)

The core algorithm

1. Maintain a search range [lo, hi] initially covering the whole array.
2. While lo ≤ hi: compute mid = lo + (hi − lo) / 2 (this form avoids the integer overflow that (lo + hi) / 2 can cause on huge indices).
3. If array[mid] == target, done. If array[mid] < target, the target must be in the right half → lo = mid + 1. Otherwise → hi = mid − 1.
4. If the loop exits without finding it, the target isn't present (and lo is where it *would* be inserted).

function binarySearch(array, target):
    lo = 0
    hi = length(array) - 1

    while lo <= hi:
        mid = lo + (hi - lo) / 2     // overflow-safe mid

        if array[mid] == target:
            return mid               // found
        else if array[mid] < target:
            lo = mid + 1             // discard left half
        else:
            hi = mid - 1             // discard right half

    return -1  // not found; lo is insertion point

The two bug magnets: the loop condition (lo ≤ hi vs lo < hi) and the updates (mid ± 1 vs mid). The invariant that keeps you honest: the target, if present, is always within [lo, hi]. Every update must *shrink* the range while preserving that invariant — using lo = mid (instead of mid + 1) is the classic infinite loop, because when lo and hi are adjacent, mid stays put and the range never shrinks. O(log n) time, O(1) space for the iterative form.

Under the hood: overflow-safe mid and the invariant

The loop invariant is the key to correctness: *if the target is present, it lies within [lo, hi]*. Prove it holds at the start (trivially true — the whole array), and that every branch preserves it. When lo > hi, the invariant means the target can't exist anywhere — the loop exits correctly. The position `lo` at exit is where the target *would* be inserted to maintain sorted order — useful for 'insert position' queries.

Finding boundaries: first and last occurrence

Plain binary search returns *some* index of the target; with duplicates you often need the *first* or *last*. The trick: when you find a match, don't stop — keep searching the appropriate side. For the leftmost occurrence, on a match record it and continue left (hi = mid − 1); for the rightmost, continue right (lo = mid + 1). Both stay O(log n). This 'find the boundary' framing is the key that unlocks the more general pattern below: binary search isn't really about *equality*, it's about finding the transition point in a monotonic condition.

// First (leftmost) occurrence
function firstOccurrence(array, target):
    lo, hi, result = 0, len-1, -1
    while lo <= hi:
        mid = lo + (hi - lo) / 2
        if array[mid] == target:
            result = mid
            hi = mid - 1        // keep looking LEFT
        else if array[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return result

// Last (rightmost) occurrence
function lastOccurrence(array, target):
    lo, hi, result = 0, len-1, -1
    while lo <= hi:
        mid = lo + (hi - lo) / 2
        if array[mid] == target:
            result = mid
            lo = mid + 1        // keep looking RIGHT
        else if array[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return result

Array: [ 1,  2,  2,  2,  3 ]
         idx:   0   1   2   3   4
Target: 2

── firstOccurrence ──────────────────────────────────────
Step 1  lo=0 hi=4  mid=2  array[2]=2  match → result=2, hi=mid-1=1
Step 2  lo=0 hi=1  mid=0  array[0]=1  < 2  → lo=1
Step 3  lo=1 hi=1  mid=1  array[1]=2  match → result=1, hi=0
        lo(1) > hi(0) → exit  → return 1  ✓ (leftmost 2)

── lastOccurrence ───────────────────────────────────────
Step 1  lo=0 hi=4  mid=2  array[2]=2  match → result=2, lo=mid+1=3
Step 2  lo=3 hi=4  mid=3  array[3]=2  match → result=3, lo=4
Step 3  lo=4 hi=4  mid=4  array[4]=3  > 2  → hi=3
        lo(4) > hi(3) → exit  → return 3  ✓ (rightmost 2)

The unifying idea: search on a monotonic predicate

Reframe binary search as finding the boundary between 'no' and 'yes' in a monotonic boolean condition. If some predicate is false, false, …, false, true, true, …, true across the range (it flips exactly once and never flips back), binary search finds the flip point in O(log n) — regardless of whether the underlying data is a sorted array at all. This reframing is what makes binary search one of the most reusable patterns in the course:

Index:     0     1     2     3     4     5     6     7
Predicate: F     F     F     F     T     T     T     T
                             ↑hi         ↑lo
                              ↗ boundary at index 4

Binary search finds the first TRUE:
  mid=3 → F → lo = 4
  mid=5 → T → hi = 4, record answer=5... keep going
  mid=4 → T → hi = 3, record answer=4
  lo(4) > hi(3) → first TRUE at index 4  ✓

This is EXACTLY the first-occurrence template applied to a boolean array.
Any problem reducible to this shape is solvable in O(log n).

• Rotated sorted array. A sorted array rotated at some pivot ([4,5,6,1,2,3]) is no longer globally sorted, but at any mid, one half *is* sorted — determine which, check whether the target lies within it, and recurse into the correct half. Still O(log n).
• Search on the answer. When you can't search a data structure but *can* check 'is answer X feasible?', and feasibility is monotonic (if X works, so does everything larger/smaller), binary search the *answer space*. Classic examples: minimum ship capacity to deliver packages in D days, smallest divisor under a threshold, the Koko-eating-bananas speed problem. You binary search over possible answers, using an O(n) feasibility check at each step → O(n log(answer range)).
• Peak finding, square roots, and floor/ceil in a sorted structure are all the same monotonic-boundary search in disguise.

Worked example: search on the answer (Koko reading piles)

You must finish reading n piles of pages within h hours; choose the minimum reading speed s (pages/hour) that finishes in time (each pile takes ⌈pages/s⌉ hours). Brute force tries every speed: slow. Instead, notice feasibility is monotonic — if speed s finishes in time, any faster speed does too — so binary search s over [1, max pile]. At each candidate speed, an O(n) pass sums the hours needed and checks it against h; narrow the range toward the smallest feasible speed. Total: O(n log(max pile)). The array was never sorted and you never 'found a value' — you searched the *space of answers* by monotonic feasibility.

function minSpeed(piles, h):
    lo = 1
    hi = max(piles)               // slowest useful speed = biggest pile

    while lo < hi:                // find the FIRST speed that works
        mid = lo + (hi - lo) / 2
        if canFinish(piles, mid, h):
            hi = mid              // mid works; try slower
        else:
            lo = mid + 1          // mid too slow; go faster

    return lo                     // lo == hi == minimum feasible speed

function canFinish(piles, speed, h):
    hours = 0
    for each pile in piles:
        hours += ceil(pile / speed)
    return hours <= h

// Example: piles=[3,6,7,11], h=8
// Search range [1..11]:
//   mid=6 → hours=ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6)=1+1+2+2=6 ≤ 8 → hi=6
//   mid=3 → hours=1+2+3+4=10 > 8 → lo=4
//   mid=5 → hours=1+2+2+3=8 ≤ 8 → hi=5
//   mid=4 → hours=1+2+2+3=8 ≤ 8 → hi=4
//   lo=hi=4 → answer: minimum speed = 4  ✓

Worked example: search in a rotated sorted array

Array (rotated): [ 4,  5,  6,  7,  0,  1,  2 ]
                   idx:  0   1   2   3   4   5   6
Target: 1

Step 1  lo=0 hi=6  mid=3  array[3]=7
        Left half [4,5,6,7] is sorted (array[lo]=4 ≤ array[mid]=7).
        Target 1 NOT in [4..7] → search right half → lo=4

Step 2  lo=4 hi=6  mid=5  array[5]=1
        Left half [0,1] (indices 4..5) is sorted.
        array[lo]=0 ≤ target=1 ≤ array[mid]=1 → target IN left half → hi=5

Step 3  lo=4 hi=5  mid=4  array[4]=0
        Left half [0] sorted. 0 ≤ 1? yes but array[mid]=0 ≠ 1, 0 < 1 → lo=5

Step 4  lo=5 hi=5  mid=5  array[5]=1  == target → FOUND at index 5  ✓

Complexity summary

Common pitfalls

• Infinite loops from wrong updates. lo = mid (instead of mid + 1) with an odd range can freeze. Ensure every branch strictly shrinks [lo, hi].
• Overflow in mid. (lo + hi) / 2 can overflow on very large indices; use lo + (hi − lo) / 2. (This exact bug lurked in a widely-used library for years.)
• Applying binary search to unsorted data. The precondition is sorted-or-monotonic. On unsorted data it silently returns wrong answers — no error, just garbage.
• Off-by-one in boundary searches. First/last-occurrence variants are where mid ± 1 details matter most; hand-trace on arrays with duplicates ([1,2,2,2,3]) before trusting the code.
• Missing the 'search on the answer' opportunity. Optimization problems with a monotonic feasibility check are begging for binary search; a nested-loop brute force there leaves a log-factor speedup unclaimed.
• Wrong loop condition for first-TRUE searches. When finding the first TRUE in a predicate, use `lo < hi` (not `lo <= hi`) so the loop terminates with lo == hi == answer.

When to use and variations

• Lower bound / upper bound. Many languages provide `lower_bound` (first index ≥ target) and `upper_bound` (first index > target) as library functions — these are the boundary-search variants. Knowing what they do under the hood saves you from reimplementing them.
• Exponential search. When the array length is unknown (an infinite or very long stream), double the search range (1, 2, 4, 8, …) until you overshoot the target, then binary search the last doubling interval — O(log position) overall.
• Ternary search. For unimodal functions (one peak), you can narrow using two midpoints per step to find the peak in O(log n). Less common but the same halving principle.

Practice problems

1. Find the first bad version (binary search on versions 1..n with an `isBad(v)` API): apply the first-TRUE monotonic search to return the minimum bad version in O(log n).
2. Minimum capacity to ship packages in D days: given an array of weights and D days, binary search the ship capacity over [max weight .. sum of weights] with an O(n) feasibility check.
3. Find peak element in an array where no two adjacent elements are equal: at mid, if array[mid] < array[mid+1], the peak is to the right (go right); otherwise go left. O(log n).

Key takeaways

• Binary search halves the search space each step: O(log n), but requires sorted or monotonic data.
• A disciplined template (invariant: target ∈ [lo, hi]; every update strictly shrinks the range) prevents the classic off-by-one and infinite-loop bugs.
• Boundary variants find first/last occurrence by continuing past a match toward the desired side.
• The deep pattern is finding the flip point of a monotonic predicate — which covers rotated arrays, peak finding, and more.
• 'Binary search on the answer' converts monotonic optimization problems into O(n log(range)) searches — one of the most powerful reusable techniques in the course.

Binary search shrank a sorted array logarithmically. The next patterns exploit sortedness and structure differently, scanning in linear time: two pointers and sliding window. Drill binary-search templates in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play