~11 min · searching-sorting, binary-search, logarithmic
Level 0Curious Beginner
0 XP0/85 lessons0/19 achievements
0/100 XP to next level100 XP to go0% complete
"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 bugs come from mixing interval conventions. Choose a closed or half-open interval, then keep the loop condition and boundary updates consistent. In fixed-width integer languages, low + (high-low)//2 avoids sum overflow. Prefer this invariant over an unattributed historical anecdote, and use a tested library such as Python's bisect in production.
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.
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.
Progress
Progress is local-only — sign in to sync across devices.