🔍 Binary Search
6th Grade 💻 Coding
Binary search is a fast way to search a sorted list: check the middle, and depending on the answer, keep going only in the half that fits, so half the list disappears with every step.
In the game “guess a number from 1 to 100” (with the hints “higher” or “lower”), you start at 50. If the answer is “higher,” only 51 to 100 are left, so you guess 75. Each guess cuts the range in half, so you’ll always find the number in 7 guesses or fewer. Guessing one number at a time could take 100.
The bigger the list, the more amazing the difference: in a list of a million items, about 20 steps are enough. There’s just one condition: the list has to be sorted. That’s how you look up a word in a printed dictionary: open it in the middle, then decide whether to go forward or back.
For example
- Looking up “orange” in a dictionary: open to the middle (around M), go to the second half, then open in the middle again, until you reach the word.
- Liam guessed his sister’s secret number (from 1 to 100) in 6 guesses because he always guessed the middle.
📌 Remember: Binary = cut in half every step. 1 to 100 takes at most 7 guesses.
Quick quiz
What do you do at each step of binary search?
At most, how many guesses do you need for a number from 1 to 100?
What is required for binary search?