Binary search — 3 real-life examples
It’s astonishing to see how so many ideas in computer science originated from real-life problems and solutions to them. In this article, I will discuss some encounters with the binary search that can happen to us outside algorithmic classes. Here, you will not find a textbook introduction to binary search. Instead, I hope to give a high-level intuition and help in deepening one’s understanding of it.
Never heard about binary search?
Do not worry. You will understand it from the examples. I taught about putting a more formal definition here, but I don’t feel that it would be better than explaining it with a real-life situation. Also, you can always find pseudocode for it on the Internet. There are literally tons of formal resources to this invaluable search.
Dictionary
Binary search is usually explained on an example with a phonebook/dictionary. Imagine having a huge dictionary with words that are alphabetically sorted. Now you would like to find the definition of word hypothalamus. How would you go about it?
One of the methods would be to start at the beginning and go word by word till you reach your goal. Well clearly this is not using anyhow the fact that words in a dictionary are sorted and in case of having big dictionary with millions of words, it would take forever. Even if I could read 3 words per second (and I don’t believe I could) it would take me more than ninety days to check one million words.
So, what’s the quicker way? We will open the dictionary in the middle and we see some word starting with m. From this, we know that hypothalamus must be before all the words starting with m — somewhere in the first half of the book. So, we take the first half and again we find the middle of it and decide in which part the hypothalamus should be. The process is repeated until the word is found.
The same approach is employed in any physical database — looking for a book in a library, going through large boxes of files in an office — it’s always about binary search.
Guessing game
This game illustrates well, that binary search can pop up anywhere. Imagine a game for two in which one of the players is trying to guess a secret number that the other guy is thinking on. The guessing player always says her try and the second answers if this secret number is the secret one, or smaller, or bigger than it.
How should one go about it?
The simple approach would be to start shouting numbers like crazy and hope for getting it right. Good luck with guessing from pool bigger than 100. This isn’t efficient at all.
So, what’s the fastest way to win?
Surprise, surprise… binary search!
The binary search way would use the fact that we know if the secret number is bigger or smaller than what we tried. So, in case of having an option of guessing from numbers 1–1000, we would pick 500, then half of the new interval and so on… this would again give the correct answer in the smallest number of steps.
Browsing the web
This one isn’t about performing binary search yourself. It’s more about showing that this particular algorithm can be found pretty much anywhere. Let’s discuss the problem of search query completion. How is it that Google is so good at it?
Surprise, surprise… it’s not binary search!
And the logic behind it is likely extremely complicated because they have to decide based on gigabytes of different data, they have about you. Nonetheless, it’s likely that in past binary search (or some idea derived from it) was used in query completion.
Let’s think about a simple program for completing queries that a user is typing. We have only his search history and we want to suggest him completion based on it. What we could do is to sequentially go through the whole think testing against every record we have. And if we are lucky, we will find something we can suggest to him. Yet this is ineffective.
On the other hand, if we had the history alphabetically sorted, we would just perform single binary search and got the result in an instance.
Now you might object that user’s history is constantly changing and keeping it sorted all the time lowers the effectiveness of the whole thing. Though this is surely true, the point isn’t to propose an implementation of a perfect auto-completer. The important thing to take away is how looking for patterns and structure in our data can dramatically improve the speed with which we can process it.
Conclusion
I hope this article improved your intuition about binary search. If you have any other examples of real-life binary search usage, please share them in the comments!
