“human beings have a strong dramatic instinct toward binary thinking, a basic urge to divide things into two distinct groups, with nothing but an empty gap in between. We love to dichotomize. Good versus bad. Heroes versus villains. My country versus the rest. Dividing the world into two distinct sides is simple and intuitive, and also dramatic because it implies conflict, and we do it without thinking, all the time.”
― Hans Rosling, Factfulness: Ten Reasons We’re Wrong About the World – and Why Things Are Better Than You Think
Consider the quite typical starting line-up for Juventus when Andrea Pirlo was the coach in the 2020/21 season:
| 1 | Wojciech Szczęsny | 30 | Rodrigo Bentancur |
| 28 | Merih Demiral | 25 | Adrien Rabiot |
| 4 | Matthijs de Ligt | 22 | Federico Chiesa |
| 16 | Juan Quadrado | 44 | Dejan Kulusevski |
| 13 | Danilo | 7 | Cristiano Ronaldo |
| 14 | Weston McKennie |
Assume that we have a sorted list of players numbers as follows:
[3, 4, 7, 13, 14, 16, 22, 25, 28, 30, 44]
And we want to find out if a certain player is playing just by their kit number. For instance, we are looking for player with the shirt number 44. Here is how binary search works:
And we want to find out if a certain player is playing just by their kit number. For instance, we are looking for player with the shirt number 44. Here is how binary search works:
- We find the element which stands on the middle index of this list
- Check if this element is equal to the number we are looking for. If yes, then problem is solved, otherwise go to the next step.
- Check if the number we are looking for is higher or lower than this element. If the desired number is higher, then it should be located to the right of the current element and vice versa.
- Continue in this manner until we either find the number of we get sure that the number does not exist in this list.
- In our example, the middle index is = 5 and the element at index 5 is 14. Because 14 < 44, it means that the kit number we are looking for must be to the right hand side of the current index. Therefore, we update our search region, and continue. More generally, if we denote the lower limit by a, the upper limit by b, and the index at the middle by c, then our search can be summarized as follows:
As it can be seen, the kit that we were looking for was found in four iterations. Bear in mind that the number that we were looking for, was the maximum in its array. If we wanted to look for it normally, starting from the left, it would have taken 11 moves (the length of the list) to be found.
This shows that binary search can increase the lookup speed quite significantly. In the best case scenario, the search would last for only one iteration, if the number we are looking for is exactly at the middle of the array. On the other hand, in the worst case scenario, if the number we are looking for is on either end of the list, like the example we just saw, then the algorithm keeps dividing the search range until the number is finally found. This means that the time complexity of binary search is O(log n), whereas the linear search has the time complexity of O(n).
It is important to note that the binary search only works if the array is sorted.
Let’s implement binary search algorithm in Python:
As a final step, we can try the function we just wrote on the list of numbers we defined at the beginning:
This will be the results:
