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.

Iterative Approach

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 = [7]

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

Time Complexity

O(log(n))

Explanation

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:

  1. 20 / 2 = 10
  2. 10 / 2 = 5
  3. 5 / 2 = 2 (floor)
  4. 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.

Space Complexity

O(1)

Explanation

Only 4 scalar variables are used: ix_low, ix_high, ix_mid, and mid_value. The size of the input array is n, but that does not count towards the space complexity of the binary search implementation.

Recursive Approach

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:

  1. All relevant information (target, array, ix_low, and ix_high) is passed to each recursive call to recursive_binary_search. ix_mid doesn’t need to be passed because it is derived from ix_low and ix_high every time.
  2. Recursive calls are being made, which implies that base cases are defined to prevent infinite recursion

Time Complexity

O(log(n))

Explanation

See the explanation above for the time complexity of the iterative approach.

Space Complexity

O(log(n))

Explanation

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.