In this article, you’ll learn about a basic algorithm, every computer scientist must know: the binary search algorithm. I have drawn the code from my NoStarch programming introductory book Python One-Liners:
Applications Binary Search
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! Thus, the impact of efficient searching is significant.
Why Naive Sorting is Bad
Say you want to search an already 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 – and repeats the same procedure until the algorithm has visited all elements.
In the worst-case (the searched value is not in the list), the naive 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 already sorted!
Algorithm Idea Binary Search
By using the fact that a list may already be partially sorted, 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.
💡 Idea: 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.
Next, we’ll binary-sort the list 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:
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 what we 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!
Python Implementation Binary Search
Here’s a practical Python 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 Formulation: 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.
Exercise: Guess the output of this code snippet!
One-Liner Binary Search Explanation
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 in four steps:
Step 1
We create a new function bs using the lambda operator with four arguments: l, x, lo, and hi.
- The first two arguments
landxdefine the sorted list and the value to be found. - The latter two arguments
hiandlodefine the minimal and the maximal index of the current sublist to be searched for the valuex.
At each recursion level, we consider a sublist (as specified by the indices hi and lo) that becomes smaller and smaller by increasing the index lo and decreasing the index hi.
After a finite number of steps, the condition lo>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.
Step 2
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
Step 3
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 hi indexmid element.
Step 4
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.
Python One-Liners Book: Master the Single Line First!
Python programmers will improve their computer science skills with these useful one-liners.
Python One-Liners will teach you how to read and write “one-liners”: concise statements of useful functionality packed into a single line of code. You’ll learn how to systematically unpack and understand any line of Python code, and write eloquent, powerfully compressed Python like an expert.
The book’s five chapters cover (1) tips and tricks, (2) regular expressions, (3) machine learning, (4) core data science topics, and (5) useful algorithms.
Detailed explanations of one-liners introduce key computer science concepts and boost your coding and analytical skills. You’ll learn about advanced Python features such as list comprehension, slicing, lambda functions, regular expressions, map and reduce functions, and slice assignments.
You’ll also learn how to:
- Leverage data structures to solve real-world problems, like using Boolean indexing to find cities with above-average pollution
- Use NumPy basics such as array, shape, axis, type, broadcasting, advanced indexing, slicing, sorting, searching, aggregating, and statistics
- Calculate basic statistics of multidimensional data arrays and the K-Means algorithms for unsupervised learning
- Create more advanced regular expressions using grouping and named groups, negative lookaheads, escaped characters, whitespaces, character sets (and negative characters sets), and greedy/nongreedy operators
- Understand a wide range of computer science topics, including anagrams, palindromes, supersets, permutations, factorials, prime numbers, Fibonacci numbers, obfuscation, searching, and algorithmic sorting
By the end of the book, you’ll know how to write Python at its most refined, and create concise, beautiful pieces of “Python art” in merely a single line.