Binary Search

What is Binary Search?

A search algorithm that repeatedly checks the middle element of a sorted list and discards the half that can't contain the target, running in O(log n) time. It's exactly the strategy behind efficiently guessing a number between 1 and 100 — never more than seven guesses, no matter how the number was chosen.

The five clues

Engineerdle #5 described Binary Search with five clues, revealed one at a time from hardest to most direct. Each clue points at a different property of the concept.

1. 01A search strategy that only works if you've done something first.
2. 02That prerequisite is a sorted list.
3. 03Each step throws away half of what's left to search.
4. 04It's the strategy behind guessing a number between 1 and 100 in at most seven tries.
5. 05An O(log n) search algorithm that repeatedly halves a sorted list until the target is found.

More Computer Science concepts

• RecursionPuzzle #15