In today’s post, we’ll learn two different ways to create a binary search in Python – using recursion and using a while loop.
Table of Contents
What is Binary Search?
First, let’s discuss what binary search is.
Binary search is an efficient algorithm for finding an element in a SORTED list. If the element is found, we return the index of the element in the list.
Suppose we have a list that is sorted in ascending order.
To do a binary search, we first compare the target with the element in the middle of the list.
If the target equals the middle element, we’ve found the element and can just return that element’s index.
On the other hand, if the target is not equal to the middle element, we need to divide the list into two halves (excluding the middle element).
If the target is greater than the middle element, we’ll search for it in the upper half in subsequent steps.
In contrast, if the target is smaller than the middle element, we’ll search for it in the lower half.
We keep dividing the list into smaller halves until we finally find the element that we want.
Example
Let’s look at an example of how binary search works.
Suppose we have the list
nums = [-5, -2, 0, 1, 2, 4, 5, 6, 7, 9]
and we want to find the target 7.
To do that using binary search, we need to keep track of three positions. Let’s call them. low, high and middle.
At the beginning,
low = 0 (index of the first element) high = 9 (index of the last element)
To find the index of the middle element, we use the formula
middle = (high + low)/2
If middle is not an integer, we round it down.
In our example,
middle = (0+9)/2 = 4.5 = 4 (rounded down)
Now, we need to compare the target with nums[middle] (i.e. nums[4]).
As the target (7) is greater than nums[4] (2), we can disregard the numbers in the lower half of nums. In other words, we only need to consider the numbers from nums[5] to nums[9].
To disregard the lower half, we update the value of low to 5.
We then proceed to calculate middle using this new value of low and repeat the steps above until we find the element we want.
Here’s a graphical illustration of how it works:
Why is Binary Search More Efficient?
In general, binary search is considered to be a very efficient search algorithm. For instance, in the example above, we only took 3 steps to find the target.
In contrast, if we do a linear search (i.e. iterating over the list elements one by one until we find our target), we’ll need 9 steps (as the target is the 9th number in the list).
Binary search is highly efficient as we discard half the list at each step and only focus on the half where the target can be in.
For a list with n elements, it can be mathematically shown that we only need a maximum of log n (base 2) steps if we do a binary search. Hence, we say that the time complexity of a binary search is O(logN).
In contrast, a linear search will require a maximum of n steps.
As such, a binary search is considered to be much more efficient than a linear search.
Cons of Binary Search
Although a binary search is more efficient than a linear search, it comes with some disadvantages.
Firstly, the list must be sorted for the algorithm to work. If the list is not sorted, we cannot determine whether the target is in the lower or upper half simply by comparing it with the middle element.
In addition, a binary search may not necessarily give us the first occurrence of the target we want. For instance, suppose nums = [7, 7, 7, 7, 7] and target = 7, a binary search will give us 2, instead of 0 (which is the index of the first occurrence). If you need to find the first occurrence of a target, a basic binary search is not appropriate.
How to do a Binary Search in Python using a while loop
Now that we know how binary search works, let’s go through two approaches that we can use to perform the search.
The first approach is to use a while loop:
def binarySearch(nums, target):
low = 0
high = len(nums) - 1
middle = 0
while low <= high:
middle = (high + low) // 2
# target equals nums[middle], return middle (index of target)
if target == nums[middle]:
return middle
# Take the upper half
elif target > nums[middle]:
low = middle + 1
# Take the lower half
else:
high = middle - 1
# If we reach this line, target is not present in nums
return -1In the code above, we first declare a function called binarySearch() on line 1.
Inside the function, we declare and initialize three variables called low, high and middle.
Next, we use a while loop (from lines 7 to 20) to repeatedly update the values of low, high and middle.
Inside the loop, if we find a case where target is equal to the middle element (line 11), we return the value of middle (which is the index of the middle element).
Else, we update the value of low if the target is in the upper half (lines 15 and 16), or high if the target is in the lower half (lines 19 and 20).
We keep doing this while low is smaller than or equal to high.
If we reach the case where low is no longer smaller than or equal to high, we have iterated over all the elements in nums and could not find the target.
Hence, we exit the while loop and reach line 23, where we return -1 to indicate that the target is not found.
How to do a Binary Search in Python using Recursion
In addition to using a while loop to do a binary search, we can also use recursion. The code below shows how this is done:
def binarySearchRec(nums, target, low, high):
if low <= high:
middle = (high + low) // 2
# target equals nums[middle], return middle (index of target)
if target == nums[middle]:
return middle
# Take the upper half
elif target > nums[middle]:
return binarySearchRec(nums, target, middle + 1, high)
# Take the lower half
else:
return binarySearchRec(nums, target, low, middle - 1)
# If we reach this line, target is not present in nums
else:
return -1Here, we define a function called binarySearchRec() with four parameters, nums, target, low and high.
Inside the function, instead of explicitly updating the values of high and low, the binarySearchRec() function calls itself recursively to perform a binary search. For each recursive call, it passes new arguments to the function to narrow the range of the list to search for the target.
For instance, suppose we call the function using the code below:
target = 7 nums = [-5, -2, 0, 1, 2, 4, 5, 6, 7, 9] print(binarySearchRec(nums, target, 0, len(nums) - 1))
When we call the binarySearchRec() function in the last statement above, Python executes the
binarySearchRec(nums, target, 0, 9)
function and calculates the value of middle (refer to line 4 in the binarySearchRec() function). As
middle = (0+9)//2 = 4
the function compares target with nums[4].
As 7 is greater than 2 (i.e. target > nums[4]), the elif block on lines 11 and 12 is executed.
This leads to the execution of binarySearchRec(nums, target, 5, 9).
Inside the execution of
binarySearchRec(nums, target, 5, 9)
we calculate the value of middle again. As
middle = (5+9)//2 = 7
and target is greater than nums[7], the elif block on lines 11 and 12 is executed again.
This leads to the execution of binarySearchRec(nums, target, 8, 9).
Inside the execution of
binarySearchRec(nums, target, 8, 9)
we calculate the value of middle again. This gives us a value of
middle = (8+9)//2 = 8
As 7 equals nums[8] (i.e. 7 = 7), something different happens now.
We no longer call the binarySearchRec() function recursively. Instead, we execute the if block on lines 7 and 8 and return the value of middle. In other words, we return 8, which is the answer that we want (i.e. the index of the target).