A Python binary search finds the position of an item in a sorted array. It divides a list in half. If a specified value is higher than the middle number, the search focuses on the right of the list. Otherwise, the search looks for the number on the left of the list.
How do you find the position of an item in a list? Binary searches have your back on that one. By using binary searches, you can easily find the position of an element inside a sorted array.
Computers are good at searching through lists to find a specific item. The rules that computers use to find items in a list are called search algorithms. One of the most popular Python algorithms is the binary search.
In this guide, we’re going to discuss what binary searches are and how they work. We’ll walk through an example of a binary search in Python so that you can learn how to write one into your programs. Let’s get started!
What is a Python Binary Search?
A Python binary search is an algorithm that finds the position of an element in an ordered array. Binary searches repeatedly divide a list into two halves. Then, a search compares if a value is higher or lower than the middle value in the list.
There are two ways you can perform a binary search. Both approaches set pointers which are used to track the highest and lowest positions at a particular point in an array.
The first approach you can use is the iterative method. In this approach, a set of statements are repeated to determine the position of an element in an array. In Python, we use a while loop for this purpose.
The other approach is the recursive method. This is where you write a function that calls itself again and again until an element in a list is found. The recursive method uses the divide and conquer approach that we discussed earlier and repeats the process of searching until an element is found.
Binary Search Tree Python: Step-by-Step
With all that talk about dividing and conquering and recursion, it can be easy to lose track of exactly how a binary search works. For that reason, we’re going to jump straight into an example of how the binary search works. Consider the following list:
| 7 | 9 | 14 | 22 | 34 |
We’re going to search for the number “22” in our list.
To start, we are going to set two pointers in our lists. One pointer will reflect the highest value in the list, and the other point will reflect the lowest value:
| Low | High | |||
| 7 | 9 | 14 | 22 | 34 |
Our next step is to find the middle element in the array, which is 14. If this value is equal to the value for which we are searching, then this value should be returned.
In this case, 14 is not the same as 22. So, our program needs to perform a comparison.
We are going to compare the number for which we are searching with the middle element of the elements on the right side of the current middle element. We’ll only do this if the number for which we are searching is greater than the middle number. Otherwise, we’ll compare the element with the middle element on the left side of the current middle element.
The number 22 is greater than 14. Our program starts to compare 22 to the middle element on the right side of our current middle element (14). In this case, that number is 22. This is equal to the number for which we are searching.
| Low | Middle | High | ||
| 7 | 9 | 14 | 22 | 34 |
We’ve found our middle value. Our program will now return the index position of that number. In this case, the index position of 22 is 3 (remember, lists are indexed starting at 0!).
How to Implement a Binary Search in Python
Let’s get our hands dirty with some Python code. We’re going to explore a Python implementation of a binary search using both the approaches that we discussed earlier: the iterative and recursive methods.
Iterative Binary Search in Python
We’ll begin with the iterative method. This is where we’ll loop through every item in our list. Then, we’ll find the middle value in the list. We will continue to do so until we have found the value for which we are looking.
Binary Search Function
Let’s start by defining a Python function for our binary search:
def findValue(numbers, number_to_find): low = 0 high = len(listnumbers - 1 while low <= high: middle = low + (high - low) // 2 if numbers[middle] == number_to_find: return middle elif numbers[middle] < number_to_find: low = middle + 1 else: high = middle - 1 return -1
Our function accepts two parameters: the list through which we want to search, and the number that we want to find in our list.
We’ve then declared two Python variables that store the default values for the lowest and highest values in the list. low is set to 0, which is the starting index value in the list. high is set to the length of the list minus one (because lists are indexed from zero).
Our next step was to declare a Python while loop. This loop runs while the lowest element is smaller than or equal to the highest number. This means that our loop will only run if our number has not yet been found.
Then, we calculate the middle number. We do this by subtracting the lowest value from the highest value. We then calculate the modulo (remainder) of that number when divided by 2. Then, we add the modulo to the value of the lowest number.
If the middle number in our list is the same as the number we want to find, we return the position of that number.
We set our new “low” number to be equal to one greater than the middle position. This happens if the middle number is less than the number that we want to find. This moves our search down to the left side of our list, like we did in our visual example earlier.
Otherwise, we set our “high” number to be equal to one less than the middle position. This moves our search to the right side of our list.
This is repeated until low is equal to or less than high. If our value is not found, we return -1. We’ll talk about why in a minute.
"Career Karma entered my life when I needed it most and quickly helped me match with a bootcamp. Two months after graduating, I found my dream job that aligned with my values and goals in life!"
Venus, Software Engineer at Rockbot
Execute the Search
Add the following code to the bottom of your program, outside the findValue function:
numbers = [7, 9, 14, 22, 34]
number_to_find = 22
final = findValue(numbers, number_to_find)
if final == -1:
print("This item was not found in the list.")
else:
print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")
We’ve started by declaring the list of items through which we want to search. Then we have specified the number we want to find, which is 22.
Next, we call our findValue() function and pass through it the list.
Here’s where the -1 comes in from earlier. If the number returned by our function is -1, that means that our item was not found in the list. Programmers often use -1 in situations like this because our search function can’t return a negative number.
Otherwise, our program prints out a message telling us the index position of that value.
Our code returns:
The number 22 was found at index position 3.
Now we know that the number 22 appears at the index position 3.
Recursive Binary Search in Python
We can also use recursion to perform a binary search. This is where we’ll define a function that keeps calling itself until a condition – our number being found – is met.
Define a Recursive Function
Like in our last example, we’ll start by writing a function that performs our binary search:
def findValue(numbers, number_to_find, low, high): if high >= low: middle = low + (high - low) // 2 if numbers[middle] == number_to_find: return middle elif numbers[middle] < number_to_find: return findValue(numbers, number_to_find, middle + 1, high) else: return findValue(numbers, number_to_find, low, middle - 1) else: return -1
Our code is somewhat similar to our last example.
We start by checking whether the highest value is greater than or equal to low. If it is, our program will return -1. Otherwise, it will start performing a binary search.
We calculate the middle number using the same approach as in the last example. First, we subtract the lowest from the highest value. Then, we calculate the modulo (remainder) of that value when divided by 2. Finally, we add the lowest number.
We’ve then written an if statement which decides how our binary search should proceed:
- If the middle number is equal to the one we are looking for, the position of that number is returned.
- If the middle number is less than the one we are looking for, our findValue() function is called again. This time, the value of low is set to be equal to one greater than our middle value.
- If the middle number is greater than the one we are looking for, the findValue() function is called. The value of “high” will be equal to one less than the middle value.
Write the Main Program
All we’ve got left to do is write our main program:
numbers = [7, 9, 14, 22, 34]
number_to_find = 22
final = findValue(numbers, number_to_find, 0, len(numbers) - 1)
if final == -1:
print("This item was not found in the list.")
else:
print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")
Our main program is the same as our earlier example bar one difference. We’re passing in two new parameters to our findValue() function: low and high.
We need to do this because our algorithm is recursive, and we can’t assign those values in our function. If we assigned the values in our function, those values would be reset every time our function executed, which would break our search algorithm.
Our code returns:
The number 22 was found at index position 3.
We’ve received the same result from earlier. In this example, we’ve used a recursive program instead of an iterative program to perform our binary search.
When Should You Use a Python Binary Search?
A binary search is an efficient way of searching through a list of numbers. This search is more efficient than a linear search. This is because the binary method cuts down your search to half as soon as you find the middle of a sorted list.
It’s important to note that a list must be ordered numerically before it can be searched using a binary search. Before you perform a binary search, make sure your numbers are sorted in ascending order.
Binary Search in Python Complexity Breakdown
What is the complexity of a binary search? That’s a good question.
The binary search algorithm has a best case complexity of O(1). This occurs when the first comparison is equal to the item for which you are searching.
The average and worst case complexity for a binary search is O(log n). This means that the length of time it takes to conduct a search increases logarithmically depending on how many items there are to search through in a list.
Conclusion
Binary searches are an efficient way to find the index position of a value in a list.
Each time a binary search is run, the search will divide the list into two parts. The search focuses on the side of the list closest to the number for which you are searching.
For each time the search is run, the amount of numbers through which the program needs to search is halved.
To learn more about Python, read our How to Learn Python guide.
About us: Career Karma is a platform designed to help job seekers find, research, and connect with job training programs to advance their careers. Learn about the CK publication.
