Binary Search
As we already know, time is a very important element of life. We all use it differently to make the best out of it. It might sound cliche but time is money. The same principle works for algorithms. The faster the runtime of the model, the less expensive it is to deploy the model. In this article, I will explain why binary search is the best approach to finding a target value in a sorted array.
You may already know that an algorithm can be designed in many different ways. But choosing the right one could save us time and space which translates to money. Let’s say you want to watch a show on Netflix (just an example) that came out recently. You type the name of the show on the search bar and Netflix will tell you if it has that show on its platform. If Netflix uses a search algorithm with linear time complexity, you will most likely wait quite a while before Netflix tells you if the requested show is available on its platform. This type of experience might make you want to switch to a different streaming platform. As you can see, Netflix can lose its customers simply because of its slow search algorithm. Let’s first understand how a search algorithm with linear time complexity works before we dive into binary search.
As the name states, an algorithm with linear time complexity is a model whose running time increases linearly as the length of the input increases. Let’s go back to our example with tv shows and apply this concept. To find the desired title in a list of titles, an algorithm with linear time complexity would check each title and compare it with the target title. If there are 25,000 tv show titles in Netflix and our requested title is located at the end of the list, an algorithm with linear time complexity would check each element until it reaches 24,999th element (because indexing starts from 0) to tell us that the title we are searching for exists. Just imagine how long it would take to look for the desired title if there were 1 million titles on the platform (this might not be possible with tv shows). At the worst-case execution, assuming that the desired title is the last in the list, it would take us 1 million iterations. As you see, the more data we input into an algorithm with linear time complexity, the more iterations it takes to perform. On the other hand, if the desired title is the first element in the list of 1 million titles, it would only take 1 iteration to find the title which is therefore called best-case execution. When designing an algorithm, we should always consider the worst-case. Let’s quantify this example. Imagine selling an algorithm that 1% of the time takes one second and 99% of the time takes an hour to execute. This would not be the best way to market the algorithm. In other words, searching for an element with linear time complexity is very slow. Here is a way to write a linear search algorithm in python:
Let’s now look at how binary search works. The logic behind the binary search is pretty simple but yet hard to comprehend at first. Here is an example: Mike and Alison are guessing numbers. Mike is thinking of a number between 1 and 100 in a sorted order 1, 2, 3, 4 … 99, 100. If Alison had to guess the number that Mike is thinking of in a few tries, she would probably start guessing from the middle. Here is how it would look:
Mike: Guess the number I’m thinking of between 1 and 100 in sorted order.
Alison: 50?
Mike: Too low.
Now Alison knows that 50 is too low and she eliminates numbers lower than 50 and continues guessing from a range between 50 and 100. Again she calls the middle number between that range.
Alison: 75?
Mike: Too high
Again Alison eliminates the numbers that are higher than 75 and continues guessing from the range between 50 and 75 exclusive.
Alison: 63?
Mike: Too high but almost there!
Alison: 57?
Mike: You got it!
Do you see the pattern? With binary search, you eliminate the half numbers in every guess. Therefore having a sorted list is very important. If I was thinking of a number between 1 and 128 it would take you exactly 7 guesses using binary search to tell me that the number I have in mind is the last element which is 128. Mathematically speaking, it would sound right to ask “how many times do I divide 128 by 2 to reach 1: 128/2= 64, 64/2=32, 32/2=16, 16/2=8, 8/2=4, 4/2=2, 2/2=1. When we reach 1, we reach the last element in the list of numbers. If you are familiar with logarithms you will look at this pattern as log2(128)=7. We can convert it to exponential form: 2⁷=128
Now you know why binary search has logarithmic time complexity.
Note: if the target value is not in the array, the function will return -1.
If we look at how both of the algorithms execute on a graph, we can see a big difference in execution times. With linear search (green line), execution time grows at the same rate as the data. Doubling the amount of data will double the amount of time needed to process it. Whereas binary search gets better and better as we input more data. For example, it takes at most 7 tries to guess a number in a list of 128 numbers. Also, it takes at most 30 tries to guess a number in a list of 1 billion numbers. As you see, it takes less execution time as we input more data. Now you can see how binary search can be time efficient and therefore relatively cheaper to use. I hope it was helpful.
If you are interested in learning how this algorithm can be implemented in real life please check out the link below:
https://github.com/miradiz/Algorithms-Data_Structures/blob/main/Building_fast_algo_project.ipynb
Thank you for reading.
