Binary Search: The Power of Halving

"Guess my number between 1 and a billion. If I tell you 'higher' or 'lower' each time, you'll nail it in about 30 guesses, not a billion. That's binary search, and that gap between 30 and a billion is the most important number in this quest."

The Algorithm

Binary search finds a target in a sorted array by repeatedly halving. Keep two pointers, low and high, bounding the region that could contain the target. Look at the mid element: if it's the target, done; if the target is larger, the answer must be in the upper half, so move low past mid; if smaller, move high below mid. Each comparison discards half the remaining region, so you reach the answer in log₂(n) steps. The 'sorted' requirement is the whole engine — it's what tells you which half to throw away.

Why log n Feels Like Magic

The power of halving is hard to overstate. A billion sorted items: linear search might check all billion; binary search checks about 30. Double the data to two billion, and binary search needs just one more step. That's the signature of O(log n) — adding a fixed amount of work each time you double the input. It's why sorted data plus binary search underpins databases, dictionaries, and version control's 'git bisect' (binary-searching commits to find the one that broke a test). When you can halve, intractable becomes instant.

Binary search halves the search region each comparison — O(log n) — but requires sorted data, which is what tells you which half to discard. A billion items resolve in ~30 steps; doubling the data adds just one step. Halving is the deepest speedup pattern in algorithms.

The Off-By-One Minefield

Binary search is famously easy to get subtly wrong — a 2011 study found bugs in many textbook implementations. The danger spots: is the loop while low <= high or <? Do you update low = mid + 1 (skipping mid, since you already checked it) or low = mid (risking an infinite loop)? Compute mid = low + (high - low) // 2 rather than (low + high) // 2 to avoid integer overflow in languages that have it. These boundary details are exactly why the pros' advice is: understand binary search deeply, but use the library (Python's bisect) for real code, where the edge cases are already correct.

Pippa's Confession

I've written binary search a dozen times and gotten the boundaries wrong on at least half of them — an infinite loop here, a missed element there. Dad's verdict was liberating: "Everyone gets binary search subtly wrong. That's why bisect exists." I still implement it to prove I understand the halving, but in real code I reach for bisect, because the off-by-one cases are a solved problem I don't need to re-solve (and re-bug) every time.

Code

Binary search by hand, and bisect for real code·python

def binary_search(arr, target):
    """Find target in a SORTED array. Returns index or -1. O(log n)."""
    low, high = 0, len(arr) - 1
    while low <= high:                       # note: <= , inclusive bounds
        mid = low + (high - low) // 2        # avoids overflow (matters in C/Java)
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1                    # discard left half (mid already checked)
        else:
            high = mid - 1                   # discard right half
    return -1

sorted_data = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(sorted_data, 11))   # 5
print(binary_search(sorted_data, 8))    # -1 (not present)

# In real code, use the library — its edge cases are already correct:
import bisect
i = bisect.bisect_left(sorted_data, 7)   # leftmost index where 7 is/would go
print("7 at index", i)                    # 3
# A billion sorted items would resolve in ~30 comparisons. That's log n.

Exercise

A sorted array has 1,000,000 elements. Roughly how many comparisons does binary search need in the worst case? If the array grew to 2,000,000, how many more comparisons? Then describe the bug that happens if you write low = mid instead of low = mid + 1 when the target is in the upper half.

Hint

log₂(1,000,000) ≈ 20 comparisons; doubling to 2,000,000 adds just ONE (≈21). Using low = mid (not mid+1) when mid isn't the target can leave low stuck at the same position forever — an infinite loop, since the region never shrinks past mid.

The Algorithm

Why log n Feels Like Magic

The Off-By-One Minefield

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0