Searching for an item is a common task in computer science as well as in our daily life. When we are trying to find something fast, choosing the right type of search method is the key. For instance, when locating a specific element among numerous sorted elements in a huge dataset, binary search is the most efficient one. New to search algorithms and want to know how binary search work in real life? From what I’ve learned from algo.monster, I will show you some real-life examples of this approach in this post.
Before presenting the examples of binary search applications, the first step is to figure out what exactly it is.
What is binary search?
A binary search algorithm works by comparing two elements each time and eliminating half the elements. And the search procedure always starts with the comparison between the target and the middle value in the array.
The best case is when the middle value is exactly what you’re looking for. Therefore, the search ends with the first step. Otherwise, it goes as the following two ways.
If the middle element of an array tends to be greater than the target value. Then, it searches the lower half of the array which is usually the left half (in ascending order). However, if the middle element is smaller, it will select the higher part of the two halves and keep on searching.
Then, the algorithm will repeat the process in the same way until the number of elements in the array becomes 1 or 2. Then, it returns the index of the item or -1 if the element happens to be absent from the original array.
The efficiency of binary search
This kind of search algorithm is famous for its efficiency in dealing with large data. The time complexity of it is O (log n) in the worst case.
During the search process, the technique downsizes the list by half after each comparison. Obviously, the search space goes like a half, then a quarter, then one out of eight, and so on. As a result, it is much faster than most algorithms.
Yet, you should know that this technique has one limitation: it won’t work with unsorted data. In other words, you can only deal with order data using it.
The efficiency of it can be perfectly shown in the worst case. Suppose the target will be the last element that you spot using binary. Say we have 100,000 elements in an ordered database. What’s the most comparisons should it go through before checking all the elements? 20.
Sounds great? And it’s more obvious when you compare the worst case of using linear search which will be 100,000 times of comparisons.
Real-life examples of binary search
Now, let’s look at some of the common examples of binary search in real life.
Dictionary
The English language contains thousands of words. And it is impossible to remember all the words. Therefore, we need a dictionary to store all the words. And dictionaries help us to find the meanings of words.
A dictionary is essentially a collection of words in alphabetic order. In other words, this is a list of well-sorted elements.
How do we look for a new word using binary search?
Let’s say we want to find the meaning of “Binary”. You can search for the word by reading the dictionary word-by-word from the beginning and comparing it with the word you are looking for. For sure, you can find this word maybe in an hour or so. Thus, this way can be time-consuming and tiresome.
Well, you can simplify this mission by using binary search. This time, you open approximately from the middle of the dictionary. Then, check what letter the letters on that page start with. Suppose you are on the page where letters begin with M. B is alphabetically smaller than M. So, you certainly won’t keep searching this word from the upper side-letter starts with N to Z.
One more thing, in this case, since B is the second letter in the alphabet, we normally automatically open it from the lower half of the dictionary. More specifically, we will try opening the page very close to the beginning.
Students’ height
Let’s say you need students to attend some activity that requires someone taller than 5 feet. And suppose students don’t know their heights.
Although you have a measurement instrument, measuring each student’s height takes much time. Again, you can use binary search to optimize the measuring process.
Firstly, ask the students to stand in line in increasing order in terms of height. In other words, the one that stands behind is taller.
Let’s say here’re the heights of them:
(4.2) (4.5) (4.7) (5.1) (5.1) (5.2) (5.3) (5.5) (5.6) (6)
How do you determine the height using binary search?
So, here’s how you pick the one to measure first. Check out the height of the student who stands in the middle.
(4.2) (4.5) (4.7) (5.1) (5.1) (5.2) (5.3) (5.5) (5.6) (6)
First measurement using binary search: student in the middle is 5.1. 5.1>5, so, you go left and spot the middle which is 4.7. Then, you go right, and only measure the students between these two students: one is 4.7 and the other is 5.1. Again, another 5.1, which means two students are 5.1 and the students behind the 4th in the line are all above 5 feet.
So, you don’t need to measure every student with binary search.
Library
This case is similar to finding a new word in the dictionary. It is impossible to search for a book in a linear fashion which goes through all thousands of the books on the shelves.
Since all books are put on the shelves alphabetically. Binary search is applicable.
Conclusion
Binary search is an efficient yet simple search method. You can use it in daily life though sometimes you don’t even notice that you’re using such a technique.
When you are looking for a name through the phonebook. You never start with the first page if the name starts with the letter K. Normally, we tend to open it in the middle and search, move lower or higher.
