{"id":19157,"date":"2020-11-15T04:46:56","date_gmt":"2020-11-15T12:46:56","guid":{"rendered":"https:\/\/careerkarma.com\/blog\/?p=19157"},"modified":"2023-12-01T04:04:03","modified_gmt":"2023-12-01T12:04:03","slug":"binary-search-python","status":"publish","type":"post","link":"https:\/\/careerkarma.com\/blog\/binary-search-python\/","title":{"rendered":"Binary Search Python: A Step-by-Step Guide"},"content":{"rendered":"\n

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.<\/em><\/p>\n\n\n\n

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.<\/p>\n\n\n\n

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<\/a> is the binary search.<\/p>\n\n\n\n

In this guide, we\u2019re going to discuss what binary searches are and how they work. We\u2019ll walk through an example of a binary search in Python so that you can learn how to write one into your programs. Let\u2019s get started!<\/p>\n\n\n\n

What is a Python Binary Search?<\/h2>\n\n\n\n

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.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

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<\/em> loop for this purpose.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

Binary Search Tree Python: Step-by-Step<\/h2>\n\n\n\n

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\u2019re going to jump straight into an example of how the binary search works. Consider the following list:<\/p>\n\n\n\n
7<\/td>9<\/td>14<\/td>22<\/td>34<\/td><\/tr><\/tbody><\/table>\n\n\n\n

We\u2019re going to search for the number \u201c22\u201d in our list.<\/p>\n\n\n\n

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:<\/p>\n\n\n\n
Low<\/td>
<\/td>
<\/td>
<\/td>		High<\/td><\/tr>
7<\/td>9<\/td>14<\/td>22<\/td>34<\/td><\/tr><\/tbody><\/table>\n\n\n\n

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.<\/p>\n\n\n\n

In this case, 14 is not the same as 22. So, our program needs to perform a comparison.<\/p>\n\n\n\n

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\u2019ll compare the element with the middle element on the left side of the current middle element.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

<\/td>
<\/td>		Low<\/td>Middle<\/td>High<\/td><\/tr>
7<\/td>9<\/td>14<\/td>22<\/strong><\/td>34<\/td><\/tr><\/tbody><\/table>\n\n\n\n

We\u2019ve 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!).<\/p>\n\n\n\n

How to Implement a Binary Search in Python<\/h2>\n\n\n\n

Let\u2019s get our hands dirty with some Python code. We\u2019re going to explore a Python implementation of a binary search using both the approaches that we discussed earlier: the iterative and recursive methods.<\/p>\n\n\n\n

Iterative Binary Search in Python<\/h3>\n\n\n\n

We\u2019ll begin with the iterative method. This is where we\u2019ll 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.<\/p>\n\n\n\n

Binary Search Function<\/h4>\n\n\n\n

Let\u2019s start by defining a Python function<\/a> for our binary search:<\/p>\n\n\n\n

def findValue(numbers, number_to_find):\n\tlow = 0\n\thigh = len(listnumbers - 1\n\n\twhile low <= high:\n\t\tmiddle = low + (high - low) \/\/ 2\n\n\t\tif numbers[middle] == number_to_find:\n\t\t\treturn middle\n\t\telif numbers[middle] < number_to_find:\n\t\t\tlow = middle + 1\n\t\telse:\n\t\t\thigh = middle - 1\n\treturn -1\n<\/pre><\/div>\n\n\n\n
Our function accepts two parameters: the list through which we want to search, and the number that we want to find in our list.<\/p>\n\n\n\n
We\u2019ve then declared two Python variables<\/a> that store the default values for the lowest and highest values in the list. low<\/em> is set to 0, which is the starting index value in the list. high<\/em> is set to the length of the list minus one (because lists are indexed from zero).<\/p>\n\n\n\n
Our next step was to declare a Python while loop<\/a>. 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.<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
If the middle number in our list is the same as the number we want to find, we return the position of that number.<\/p>\n\n\n\n
We set our new \u201clow\u201d 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.<\/p>\n\n\n\n
Otherwise, we set our \u201chigh\u201d number to be equal to one less than the middle position. This moves our search to the right side of our list.<\/p>\n\n\n\n
This is repeated until low is equal to or less than high. If our value is not found, we return -1. We\u2019ll talk about why in a minute.<\/p>\n\n\n\n
Execute the Search<\/h4>\n\n\n\n
Add the following code to the bottom of your program, outside the findValue<\/em> function:<\/p>\n\n\n\n
numbers = [7, 9, 14, 22, 34]\nnumber_to_find = 22\n\nfinal = findValue(numbers, number_to_find)\n\nif final == -1:\n\tprint("This item was not found in the list.")\nelse:\n\tprint("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")\n<\/pre><\/div>\n\n\n\n
We\u2019ve 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.<\/p>\n\n\n\n
Next, we call our findValue()<\/em> function and pass through it the list.<\/p>\n\n\n\n
Here\u2019s 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\u2019t return a negative number.<\/p>\n\n\n\n
Otherwise, our program prints out a message telling us the index position of that value.<\/p>\n\n\n\n
Our code returns:<\/p>\n\n\n\n
The number 22 was found at index position 3.<\/pre><\/div>\n\n\n\n
Now we know that the number 22 appears at the index position 3.<\/p>\n\n\n\n
Recursive Binary Search in Python<\/h3>\n\n\n\n
We can also use recursion to perform a binary search. This is where we\u2019ll define a function that keeps calling itself until a condition \u2013 our number being found \u2013 is met.<\/p>\n\n\n\n
Define a Recursive Function<\/h4>\n\n\n\n
Like in our last example, we\u2019ll start by writing a function that performs our binary search:<\/p>\n\n\n\n
def findValue(numbers, number_to_find, low, high):\n\tif high >= low:\n\t\tmiddle = low + (high - low) \/\/ 2\n\n\t\tif numbers[middle] == number_to_find:\n\t\t\treturn middle\n\t\telif numbers[middle] < number_to_find:\n\t\t\treturn findValue(numbers, number_to_find, middle + 1, high)\n\t\telse:\n\t\t\treturn findValue(numbers, number_to_find, low, middle - 1)\n\t\n\telse:\n\t\treturn -1\n<\/pre><\/div>\n\n\n\n
Our code is somewhat similar to our last example.<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
We\u2019ve then written an if<\/em> statement which decides how our binary search should proceed:<\/p>\n\n\n\n