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). Binary search is a great tool to keep in mind for array problems.
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 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 binary search 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.
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)) def binary_search_helper(nums, key, start_idx, end_idx): middle_idx = (start_idx + end_idx) // 2 if start_idx == end_idx: return None if nums[middle_idx] > key: return binary_search_helper(nums, key, start_idx, middle_idx) elif nums[middle_idx] < key: return binary_search_helper(nums, key, middle_idx + 1, end_idx) else: return middle_idx
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) while right_idx > left_idx: middle_idx = (left_idx + right_idx) // 2 if nums[middle_idx] > key: right_idx = middle_idx elif nums[middle_idx] < key: left_idx = middle_idx + 1 else: return middle_idx return None
Binary search completes in O(log N) time because each iteration decreases the size of the list by a factor of 2. Its space complexity is constant because we only need to maintain two pointers to locations in the list. Even the recursive solution has constant space with tail call optimization.