Core · Module 9 · Lesson 1 of 4
Binary search without off-by-one bugs
Binary search halves a sorted range at every step, so a billion items need about 30 comparisons. Writing it correctly comes down to one decision: what exactly the range means, and keeping that true.
By the end you can
- Implement binary search on a half-open range with a stated invariant
- Explain why it takes about log₂ n steps and always terminates
- Avoid the classic bugs: overflow, infinite loops and boundaries that don't match the loop condition
Builds on Growth rates and Big-O, Index arithmetic.
01 · A question first
When Jon Bentley asked professional programmers to write a binary search, he found that about nine in ten of their programs had bugs, and a bug in Java's own library version went unnoticed for nine years. The idea fits in a sentence. Where do the bugs hide?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Halving the range
- Choose a meaning for the range
- Termination and overflow
- Testing a binary search
- Sorted array or hash table?
- Use the library when you can
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Something wrong with this lesson? Report a problem