Binary Search - codepath/compsci_guides GitHub Wiki

Binary search is a method for locating an element in a sorted list efficiently. Searching for an element can be done naively in O(N) time, but binary search speeds it up to O(log N) in the worst case. Binary search is a great tool to keep in mind for array problems.

Algorithm

In binary search, you are provided a list of sorted numbers and a key. The desired output is the index of the key, if it exists and None if it doesn't.

Binary search is a recursive algorithm. The high-level approach is that we first examine the middle element of the list. The value of the middle element determines whether to terminate the algorithm (found the key), recursively search the left half of the list, or recursively search the right half of the list.

The pseudocode for binary search:

def binary_search(nums, key):
    if nums is empty:
        return None
    if middle element is equal to key:
        return middle index
    if middle element is greater than key:
        binary search left half of nums
    if middle element is less than the key:
        binary search the right half of nums

There are two canonical ways of implementing binary search: recursive and iterative. Both solutions utilize two pointers that track the start and end of the portion within the list that we are searching.

Recursive Binary Search

The recursive solution utilizes a helper function to keep track of pointers to the section of the list we are currently examining. The search either completes when we find the key, or the two pointers meet.

def binary_search(nums, key):
    return binary_search_helper(nums, key, 0, len(nums) - 1)
 
def binary_search_helper(nums, key, start_idx, end_idx):
    if start_idx > end_idx:
        return None
    middle_idx = (start_idx + end_idx) // 2
    if nums[middle_idx] > key:
        return binary_search_helper(nums, key, start_idx, middle_idx - 1)
    elif nums[middle_idx] < key:
        return binary_search_helper(nums, key, middle_idx + 1, end_idx)
    else:
        return middle_idx

Iterative Binary Search

The iterative solution manually keeps track of the section of the list we are examining, using the two-pointer technique. The search either completes when we find the key, or the two pointers meet.

def binary_search(nums, key):
    left_idx, right_idx = 0, len(nums) - 1
    while left_idx <= right_idx:
        middle_idx = (left_idx + right_idx) // 2
        if nums[middle_idx] > key:
            right_idx = middle_idx - 1
        elif nums[middle_idx] < key:
            left_idx = middle_idx + 1
        else:
            return middle_idx
    return None

Runtime and Space Complexity

The iterative binary search has O(log N) time complexity because each iteration decreases the size of the list by half. Its space complexity is O(1) because it only uses a constant amount of space for the pointers.

The recursive binary search also has O(log N) time complexity, but its space complexity is O(log N) due to the call stack, as Python does not guarantee tail call optimization.

Example problems

Video walkthrough