In this article, we will be discussing the Python Binary Search Algorithm in complete detail. We will start with it’s explanation, followed by a complete solution which is then explained by breaking it down into steps and explaining each of them separately.
Methodology
Binary search works off the simple concept of halving sorted lists to find the required value. Let’s say you wanted to find the number 30, in a list containing 100 values from 1 to 100 (sorted). First, you will find the value at the mid point (50), and check to see if the search value (30) is greater or less then it. If it is less, it means the value is located somewhere in the first half of the list.
Hence, we will ignore the second half of the list. We will then proceed to continuously half the list, while comparing mid points, until the mid value is equal to the search term (when only one value is left).
And of course, it’s easy to see why the list or array, needs to be sorted for this to work.
Binary Search Solution
Here you can find our solution to the Binary Search Algorithm. You can also find a recursive solution included towards the end of this tutorial.
The Binary search function we made takes two inputs, the array in which we will be searching and the value which we will be searching for. In the first line of the function, we initialize left to 0 (the left most index), and right to the length of the array, minus 1 (the right most index of the array).
The main execution takes place in the while loop, where iterate over the array until the right index becomes smaller than the left. This only happens when the array has been completely search through.
def binary_search(a, x):
left, right = 0, len(a) - 1
while left <= right:
mid = left + (right - left) // 2
if a[mid] == x:
return mid
elif x < a[mid]:
right = mid - 1
else:
left = mid + 1
return -1
We first calculate the mid index, and then begin a series of if statement checks. If the value at the mid point is equal to the search value, we return the mid index.
In the other two if and else statements lies the core concept behind binary sort. If the search value is less than mid, we adjust the position of the right index to mid - 1, which is the index right before the mid. We basically just cut down the search range in the array by half, by changing the indexes to include only the first half of the array.
In the else statement, we do the opposite. It will only trigger if the search value is greater than the mid value. If it runs, it will adjust the left to mid + 1. This narrows our search range to the second half. The while loop then repeats itself, continously halving the array till we find our value.
You may be wondering why we did this (the below line) instead of mid = (left + right) / 2.
mid = left + (right - left) // 2
Here is the code that is going to actually call the binary_search function.
if __name__ == '__main__':
value = int(input())
array = [1, 4, 7, 9, 10, 15, 20, 23, 31, 43]
print(binary_search(array, value))
If the search value is not found, -1 is printed out onscreen, otherwise the search value will be printed out.
Explanation
In this section we’ll try out a real life example of the Binary Search algorithm in Python, by individually breaking down and explaining each step.
We’ll use the above array, with numbers from 1 to 20. Remember, that the array must be sorted for binary search to work. In this example, the search value we are looking for is 9.
The first thing to do is to find the mid point. Using the formula left + (right - left) // 2 will give us 0 + ( 19 ) // 2 which is equal to 9. The value at array[9] is 10, hence it’s the mid point.
I’m currently showing the mid point by highlighting it in red. We now have to make the comparison between the search value and the mid point. If the search value is less (which it is in this case), then we change the right variable to point to the value before the mid value.
As shown in the above diagram, the two solid arrows represent the left and right positions after we adjust the positions.
In short, we are left with the above array. (The other values are still there obviously, but not relevant to us now, so I left them out). Once again we’ll pick a new mid point, which happens to be 5 here.
This time the search value was greater than the mid point, we so changed the left position from 0 to mid + 1. We are now left with the above 4 values, where the mid point is 7.
We will continue onwards with this process, until we are left with just a single value, which is our search term. It will become the new mid point, and will be caught by the following if statement in the binary search algorithm.
This is also the point where the right value becomes smaller than the left. Think of it this way, the mid index is 0 right? And since there is only one value, the left and right both point to the 0th index too. So when we do right = mid - 1 or the left = mid + 1, the value of left will become greater than the right, breaking the loop.
if a[mid] == x:
return mid
It will return the mid index, which is also the index for the search term, indicating that we found it and giving you it’s position in the array.
There is also the case where we search through the entire array, but never found the search term. In this case, returning -1 is a fairly standard practice.
Recursive Binary Search
Here is the Recursive solution for the Binary Search Algorithm in Python. It’s mostly the same thing, but without the While loop, which has been replaced by recursive calls. The if statements remain the same in their logic, but they have the added duty of making recursive calls.
def binary_search(arr, x, left, right):
if right >= left:
mid = left + (right - left) // 2
if arr[mid] == x:
return mid
elif x < arr[mid]:
right = mid - 1
return binary_search(arr, x, left, right)
else:
left = mid + 1
return binary_search(arr, x, left, right)
else:
return -1
if __name__ == '__main__':
value = int(input())
array = [1, 4, 7, 9, 10, 15, 20, 23, 31, 43]
print(binary_search(array, value, 0, len(array) - 1))
In the recursive calls, the only thing that changes is the left and right parameters, which keep growing narrower. Eventually it reaches a point where the right index becomes smaller than the left, which will cause the function to return -1, because if the value had been found, it would have returned earlier.
This marks the end of the Python Binary Search Algorithm. Any suggestions or contributions for CodersLegacy are more than welcome. Questions regarding the tutorial content can be asked in the comments section below.