In this article, you’ll learn about a basic algorithm, every computer scientist must know: the binary search algorithm.
If you just want to try the algorithm in Python, feel free to play with our interactive Python shell:
The algorithm has important practical applications in many basic data structures such as sets, trees, dictionaries, bags, bag trees, bag dictionaries, hash sets, hash tables, maps, and arrays. You use these data structures in every single non-trivial program (and in many trivial ones as well). The impact of efficient searching is massive.
For example, say you want to search a sorted list for value 56. The naïve algorithm starts with the first list element, checks whether it’s equal to the value 56, and moves on to the next list element – until the algorithm has visited all elements. In the worst-case (the searched value is not in the list), the algorithm goes over all list elements. For example, searching a sorted list with 10,000 elements would take approximately 10,000 operations to check each list element for equality with the searched value. In algorithmic theory language, we say that the runtime complexity is linear in the number of list elements. This is by no means optimal – because the algorithm does not leverage all the available information to achieve the greatest efficiency. After all, the list is sorted! By using this fact, we can create an algorithm that “touches” only a few elements in the list and still knows with absolute certainty whether an element exists in the list – or not. In fact, instead of traversing all list elements of a given sorted list, the binary search algorithm traverses only log2(n) elements (logarithm of base 2). In other words, we can search the same list of 10,000 elements using only log2(10,000) < 14 instead of 10,000 operations!
How to search a list in logarithmic runtime? The most popular algorithm that solves this problem is the binary search algorithm. The idea is simple: assume the list is sorted in an ascending manner. The algorithm starts checking the middle element first. If our searched value is smaller than this middle element, we know that all elements between the middle and the last list elements are larger than the searched value (because of the sorted property). The searched element will not exist in this half of the list so we can immediately reject half of the list elements with a single operation. Similarly, if the searched value is larger than the middle element, we can reject the first half of the list elements. Now, we simply repeat this procedure – halving the effective list size of elements to be checked in each step of the algorithm. Here’s a visual example:
Figure: Example of the binary search algorithm.
The figure shows the binary search algorithm at work. Say you want to find the value 56 in the sorted list of eight integer values. Recap that our goal is to traverse the sorted list in logarithmic time so we cannot afford to touch each element in the list. The binary search algorithm in the graphic repeatedly probes the element x in the middle of the list (rounding down). There are three cases:
- Element x is larger than the searched value 56. In this case, the algorithm ignores the right part of the list as all elements are larger than 56 as well because the list is already sorted.
- Element x is smaller than the searched value 56. This is
the whatwe observe in the figure. Here, the algorithm ignores the left part of the list as they are smaller as well (again, using the property that the list is already sorted).
- Element x is equal to the searched value 56. You can see this case in the last line in the figure. Congratulations, you have just found the searched element in the list!
In each phase of the algorithm, the search space is reduced by half. This means that after a logarithmic number of steps, we have found the element! Here’s a practical implementation of the binary search algorithm:
def binary_search(lst, value): lo, hi = 0, len(lst)-1 while lo <= hi: mid = (lo + hi) // 2 if lst[mid] < value: lo = mid + 1 elif value < lst[mid]: hi = mid - 1 else: return mid return -1 l = [3, 6, 14, 16, 33, 55, 56, 89] x = 56 print(binary_search(l,x)) # 6 (the index of the found element)
Listing: The iterative binary search algorithm.
The algorithm takes as arguments a list and a value to be searched. Then, it repeatedly halves the search space using the two variables lo and hi. Those variables define the interval of possible list elements where the searched value could exist. The former variable lo defines the start index and the latter variable hi defines the end index of the interval. We repeatedly check in which case of the above cases the mid element falls and adapt the interval of potential elements accordingly by modifying the lo and hi values as described above. While this algorithm is a perfectly valid, readable, and efficient implementation of the binary search algorithm, it’s not a one-liner solution, yet!
The Recursive Binary Search Algorithm
Problem: Implement the binary search algorithm in a single line of code!
## The Data l = [3, 6, 14, 16, 33, 55, 56, 89] x = 33 ## The One-Liner bs = lambda l, x, lo=0, hi=len(l)-1: -1 if lo>hi else \ (lo+hi)//2 if l[(lo+hi)//2] == x \ else bs(l, x, lo, (lo+hi)//2-1) if l[(lo+hi)//2] > x \ else bs(l, x, (lo+hi)//2+1, hi) ## The Results print(bs(l, x))
Listing: One-liner solution using basic array arithmetic.
Guess the output of this code snippet!
How It Works
For readability, I’ve broken this “one-liner” solution into four lines – even if you could write it in a single line of code. It’s often better to limit the length of a single line because it makes it easier for readers to understand the code.
I used a recursive way of defining the binary search algorithm.
(I) We create a new function bs using the lambda operator with four arguments: l, x, lo, and hi. The first two arguments l and x define the sorted list and the value to be found. The latter two arguments hi and lo define the minimal and the maximal index of the current sublist to be searched for the value x. At each recursion level, we consider a sublist (as specified by the indices hi and low) that becomes smaller and smaller by increasing the index low and decreasing the index hi. After a finite number of steps, the condition low>hi holds True. This is the base case of our recursion and if we haven’t found the searched element x by now, we return -1 indicating that no such element exists.
(II) We return the index (lo+hi)//2 of the mid element (in the specified sublist) if this element is the searched value. Note that we use integer division to round down to the next integer value that can be used as
(III) However, if the mid element is larger than the searched value, there is no need to search all elements on the right of the mid element. These elements will be larger too because the list is sorted. Hence, we call the function recursively but adapt the
(IV) Similarly, if the mid element is smaller than the searched value, there is no need to search all elements on the left of the mid element. Hence, we call the function recursively but adapt the lo index to consider only list elements on the right of the mid element.
Thus, when searching for the value 33 in the list [3, 6, 14, 16, 33, 55, 56, 89], the result is the index 4.
I hope that this article improved your general code understanding skills regarding various Python features such as conditional execution, basic keywords, arithmetic operations, and the important topic of programmatic sequence indexing. But more importantly, you’ve learned how to use recursion to make complex problems easier.
Where to Go From Here?
Many coders never feel like they have NOT learned enough to apply their skills in the real world. That’s a huge mistake. Don’t be one of those coders — because it’s a self-fulfilling prophecy! They are stuck studying toy projects forever and will never be successful.
Instead, set yourself on a clear path to mastery with a strict 70/30 training plan: 70% practical code projects and 30% theory. Many students have already followed this training plan — and have accelerated their skill level like nothing before. Create your new high-income skill Python and reach Python freelancer level in a few months! The link leads you to my in-depth Python program for upcoming freelancers and Python professionals.
While working as a researcher in distributed systems, Dr. Christian Mayer found his love for teaching computer science students.
To help students reach higher levels of Python success, he founded the programming education website Finxter.com. He’s author of the popular programming book Python One-Liners (NoStarch 2020), coauthor of the Coffee Break Python series of self-published books, computer science enthusiast, freelancer, and owner of one of the top 10 largest Python blogs worldwide.
His passions are writing, reading, and coding. But his greatest passion is to serve aspiring coders through Finxter and help them to boost their skills. You can join his free email academy here.