Binary Search

Everyone knows binary search on a sorted array. The reason it’s a pattern worth a lesson is the advanced forms — finding boundaries, rotated arrays, and especially “search on the answer,” which interviewers love.

The idea and the template

Look at the middle. If it’s the target, done. If the target is bigger, it can only be in the right half, so discard the left; if smaller, discard the right. Each step halves the space → O(log n).

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1           # target is in the right half
        else:
            hi = mid - 1           # target is in the left half
    return -1
# binary_search([1,3,5,7,9,11], 7) -> 3

Write this template once, carefully (lo <= hi, mid+1, mid-1), and trust it — boundary bugs are the main danger.

Finding boundaries (first / last position)

To find the first occurrence, don’t stop at a match — record it and keep searching left; for the last, keep searching right:

def first_position(a, target):
    lo, hi, ans = 0, len(a) - 1, -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            ans = mid; hi = mid - 1     # found one, but look further left
        elif a[mid] < target: lo = mid + 1
        else:                 hi = mid - 1
    return ans

Rotated sorted array

In a rotated array ([4,5,6,7,0,1,2]), at any mid one half is still sorted. Figure out which half is sorted, check if the target lies within it, and recurse into the right side:

def search_rotated(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target: return mid
        if a[lo] <= a[mid]:                      # left half is sorted
            if a[lo] <= target < a[mid]: hi = mid - 1
            else:                        lo = mid + 1
        else:                                    # right half is sorted
            if a[mid] < target <= a[hi]: lo = mid + 1
            else:                        hi = mid - 1
    return -1

The power move: binary search on the answer

This is the pattern interviewers really test. When you can ask a monotonic yes/no question — “can we do it with value X?” where bigger X is always “yes” (or always “no”) — you can binary-search the answer value itself, even when there’s no sorted array in sight. Example — Koko eating bananas (smallest eating speed to finish in H hours):

import math
def koko(piles, H):
    lo, hi = 1, max(piles)
    while lo < hi:
        speed = (lo + hi) // 2
        hours = sum(math.ceil(p / speed) for p in piles)
        if hours <= H: hi = speed        # fast enough → try slower
        else:          lo = speed + 1    # too slow → go faster
    return lo
# koko([3,6,7,11], 8) -> 4

The tell for this: “minimise the maximum” / “maximise the minimum” / “smallest X such that a condition holds” — split array largest sum, minimum capacity to ship packages, aggressive cows, etc.

Step-by-step walkthrough

Trace Binary Search for 15 in [-1, 0, 3, 5, 9, 12, 15, 20]. Each step looks at the middle and throws away the half that cannot contain the target.

Found at index 6 in 3 steps. Eight elements need at most ⌈log₂ 8⌉ + 1 = 4 probes; a million need about 20.

When to reach for it

Signals: the data is sorted (or rotated-sorted); you need a boundary (first/last, insertion point); the answer space is monotonic and you’re asked to minimise a maximum or find the smallest feasible value; or the constraints go up to 10⁹ (which screams O(log n)).

Pitfalls

• Off-by-one and infinite loops. lo <= hi vs lo < hi, mid vs mid+1/mid-1 — a single wrong boundary loops forever or misses the answer. Pick a template and keep it.
• Integer overflow (other languages). Use lo + (hi-lo)//2 in Java/C++. (Python is fine.)
• Missing the “search on answer” framing. If you don’t see a sorted array, ask: is there a value I can guess, with a monotonic yes/no check? That’s the hidden binary search.

Recap

Binary search halves a sorted/monotonic space → O(log n). Learn the template cold, then extend it: boundaries (keep going after a match), rotated arrays (one half is always sorted), and the power move — binary search on the answer (guess a value, check a monotonic condition) for “minimise the maximum” problems. Signal: sorted, boundary, minimise-the-max, or n up to 10⁹.

Practice: 13 solved problems on binary search → — cover each one, solve it yourself, then check the tested code.

Next: Lesson 11 — Linked-List Reversal.