- I want to explain binary search by using an everyday example (practical/relateable )
Binary Search in an Everyday Example
One of my favorite metaphors for binary search is a guessing game. Let’s say you and your friend (Karen) are playing a guessing game to see if you can guess the number Karen is thinking. The number is between 1 -100. If you guess wrong, she’ll tell you either too high or too low.
FYI Karen is thinking of the number 18, but let's pretend we didn’t know.
There are usually about 4 popular strategies.
- Start guessing random numbers, hoping you get it in a few tries.
- You guess each number in the order or reverse order.
- Since you and Karen go way back, you guess her favorite number or birth month.
- You try to eliminate as many possible options to make a more accurate guess. So you start by guessing the number 50. Whether Karen says it's too high or too low, it literally cuts your options down by 50%. This is where we start thinking like a binary search algorithm.
Karen responds, “50 is too high.” So then you guess 25 because you want to cut the options down by 50% again. Karen says, “too high.”
Again you want to eliminate the most options possible, so you choose half of 25, 12.5. The convention in binary search is to round down(although you can round up too), so you say 12. Karen says, “ Too low,” for the first time! So that means we are getting closer.
Since there are 12 options left, 12/2 would be 6. Since the last guess was 12 and it was too low, If you move up 6 boxes up from 12. We then land on 18, and Karen says, “that we guessed right! ” We got the answer in 5 guesses, which is pretty fast.
Imagine how many more guesses it would have taken if we guessed each number beginning at 1, and Karen was thinking of the number 100 instead. It would have taken forever. That would have been an example of a simple search algorithm that is much slower than a binary search.
What Exactly is Binary Search?
Binary search is an algorithm strategy to obtain the target number within an ordered array. Binary search will not work with an unordered array! Thinking through binary search, we want to eliminate as many options as possible by cutting the list by half until it gets through the entire list and checking if we hit the target number or not. It’s a fast algorithm with a worst-case O(log n) performance and a beneficial tool for tackling complex future algorithms.
The example above returns the target number being karensNum if present, else it returns -1.
Thank you for reading the article! I hope you found it helpful.