Binary search is a fast way to figure out if a certain element exists in a sorted list of elements. Sorted is a really important keyword here. Binary search only works with sorted lists.
There’s at least two approaches to implementing binary search: iterative and recursive.
I think the iterative approach is preferable in all cases because it has the same time complexity as the resursive approach while maintaining constant space complexity.
The recursive approach, on the other hand, needs to add log(n) frames to the stack in the worst case. It is simply unneccesary to consume any more than constant space with an iterative approach.
Both of the implementations below return the index of the target element. If the target element doesn’t exist, then -1 is returned.
from math import floor normal_input = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] empty_list_input =  single_element_input =  def iterative_binary_search(target, array): ix_low = 0 ix_high = len(array) - 1 while ix_low <= ix_high: ix_mid = floor((ix_low + ix_high) / 2) mid_value = array[ix_mid] if mid_value == target: return ix_mid if target > mid_value: ix_low = ix_mid + 1 else: ix_high = ix_mid - 1 return -1 assert iterative_binary_search(16, normal_input) == 15 assert iterative_binary_search(5, empty_list_input) == -1 assert iterative_binary_search(7, single_element_input) == 0
Each time through the while loop the size of the remaining elements that we are searching through is reduced by half. Assuming 20 elements in the sorted array, the pool of candidate elements decreases like this:
- 20 / 2 = 10
- 10 / 2 = 5
- 5 / 2 = 2 (floor)
- 2 / 2 = 1
In the worst case the binary search takes 4 steps. The worst case is when the target element is the last element we look at. Note that n=20, and 4 is roughly equal to log2(20). log2(20) is ~4.32.
Only 4 scalar variables are used:
mid_value. The size of the input array is
n, but that does not count towards the space complexity of the binary search implementation.
def recursive_binary_search(target, array, ix_low, ix_high): if ix_low > ix_high: return -1 ix_mid = floor((ix_low + ix_high) / 2) mid_value = array[ix_mid] if mid_value == target: return ix_mid if target > mid_value: return recursive_binary_search(target, array, ix_mid + 1, ix_high) else: return recursive_binary_search(target, array, ix_low, ix_mid - 1) assert recursive_binary_search(16, normal_input, 0, len(normal_input) - 1) == 15 assert recursive_binary_search(5, empty_list_input, 0, len(empty_list_input) - 1) == -1 assert recursive_binary_search(7, single_element_input, 0, len(single_element_input) - 1) == 0
This solution looks similar to the iterative solution with two big differences:
- All relevant information (
ix_high) is passed to each recursive call to
ix_middoesn’t need to be passed because it is derived from
- Recursive calls are being made, which implies that base cases are defined to prevent infinite recursion
See the explanation above for the time complexity of the iterative approach.
There are log(n) recursive calls to
recursive_binary_search made in the worst case. Each of these recursive calls adds a frame to the stack, making the space complexity O(log(n)) based on the space consumed by the stack.