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 of these methods 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 Divide and Conquer Algorithm?
Divide and conquer. It sounds like something from the medieval times!
In programming, you don’t divide and conquer castles or homesteads. It’s a way of referring to a special way of solving a recursive problem. Recursive problems are where the solution to a problem depends on solutions of smaller examples of the same problem.
A divide and conquer algorithm solves a problem by breaking the problem down into smaller problems, solving those mini-problems, and then combining the result to get an output.
What is a Binary Search?
A binary search is an algorithm that finds the position of an element in an ordered array. It is a common and standard computer science algorithm.
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.
When Should You Use a 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 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: 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:
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:
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 – 22 – then this value should be returned.
In this case, 14 is not the same as 22. So, our program needs to perform a comparison.
If the number for which we are searching is greater than the middle number, 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. 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, so 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.
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
We’ll begin with the iterative method. This is where we’ll loop through every item in our list, find its middle value, and continue to do so until the search is complete.
Let’s start by defining a 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 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 while loop which 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, and add it 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.
If the middle number is less than the number that we want to find, we set our new “low” number to be equal to one greater than the middle position. This moves our search down to the left side of our list, like we did in our visual example earlier. This means that our program will only search through numbers it knows are close to the number for which we are searching.
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.
Add the following code to the bottom of your program, outside the
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 through which we want to search and the number that we want to find.
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
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.
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 or not 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: we subtract the lowest from the highest value, calculate the modulo (remainder) of that value when divided by 2, and then 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
lowis 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.
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.
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.
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 and focus on the side of the list closest to the number for which you are searching.
This means that for each time the search is run, it will reduce the amount of numbers through which the program needs to search by two.
Now you’re equipped with the knowledge you need to write binary searches in Python using both an iterative and recursive function!