Looking for a name in a sorted contact list? Instead of checking every entry, open near the middle. If the name you want comes later alphabetically, you can discard the entire first half. Repeat, and the remaining search space shrinks quickly.
The key idea: keep an invariant
Maintain a range that could still contain the target. At each step, choose a midpoint and compare it with the target. When the midpoint is too small, move the lower boundary past it; when it is too large, move the upper boundary before it. Every iteration must make the range smaller.
For an inclusive range low..high, a safe midpoint expression is low + floor((high - low) / 2). This avoids possible overflow from adding two very large indices first.
Why it is fast
Each comparison cuts the remaining candidates approximately in half. After about log₂(n) comparisons, only one candidate remains, so the search takes O(log n) time. The collection must be sorted, and random-access arrays make midpoint access efficient.
Common mistakes
- Forgetting to move beyond the midpoint, which can create an infinite loop.
- Mixing inclusive and exclusive range boundaries.
- Stopping at any match when the task asks for the first or last duplicate.
Write down what your boundaries mean before coding. A clear invariant is what turns binary search from a trick into a reliable method.