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, were going to discuss what binary searches are and how they work. Well walk through an example of a binary search in Python so that you can learn how to write one into your programs. Lets 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.
81% of participants stated they felt more confident about their tech job prospects after attending a bootcamp. Get matched to a bootcamp today.
Find Your Bootcamp MatchThe average bootcamp grad spent less than six months in career transition, from starting a bootcamp to finding their first job.
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, were going to jump straight into an example of how the binary search works. Consider the following list:
| 7 | 9 | 14 | 22 | 34 |
Were 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. Well only do this if the number for which we are searching is greater than the middle number. Otherwise, well 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.
- Career Karma matches you with top tech bootcamps
- Get exclusive scholarships and prep courses
| Low | Middle | High | ||
| 7 | 9 | 14 | 22 | 34 |
Weve 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
Lets get our hands dirty with some Python code. Were 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 Searchin Python
Well begin with the iterative method. This is where well loop through every item in our list. Then, well 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
Lets start by defining a Python function for our binary search:
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.
Weve 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 weve got left to do is write our main program:
Our main program is the same as our earlier example bar one difference. Were passing in two new parameters to our findValue[] function: low and high.
We need to do this because our algorithm is recursive, and we cant 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:
Weve received the same result from earlier. In this example, weve 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.
Its 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? Thats 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.