Cutting the problem in half
Binary search needs a sorted array. You look at the middle element, compare it to the target, and discard the half that cannot contain the answer. Each comparison halves the remaining range, so the search shrinks fast.
The core loop
- Keep two bounds, a low and a high, marking the live range.
- Compute the middle index between them.
- If the middle value equals the target, you are done.
- If the target is smaller, move high just below the middle; if larger, move low just above it.
- Stop when low passes high, meaning the target is absent.
Where bugs hide
- Computing the middle as low plus high can overflow in fixed width integers; add half the gap to low instead.
- Updating bounds to the middle rather than just past it can loop forever.
- Decide up front whether high is inclusive or one past the end and stay consistent.
Because each step removes half the candidates, even a billion element array resolves in about thirty comparisons.
Key idea
Binary search exploits sorted order to throw away half the candidates per comparison, but only careful bound updates keep it correct and terminating.