Binary Search

Preconditions

• It is possible to rule out half of the solution space at each step. Though this usually means a sorted array, it can be used outside of that context too.

Implementation

def binary_search(arr, target):
    l, r = 0, len(arr) - 1
    while l <= r:
        # using (l + r) // 2 could cause an overflow
        m = l + (u - l) // 2
        if arr[m] < t:
            l = m+1
        elif arr[m] == t:
            return m
        else:
            r = m - 1
    return -1

Binary search problems can get quite complex with infinite loops etc if you’re not careful. See An approach to writing bug-free Binary Search code

Problems

• Find minimum in rotated sorted array: focus on the endpoints of the array
• Integer square root: the set of integers is sorted, which can be used to narrow the solution down

Bisect Module

The bisect module implements functions for Binary Search. If arr is a sorted list and x is the target value:

• bisect.bisect_left(arr, x): returns the index of the first element that is not less than x. If all elements in arr are less than x, the return value is len(arr)
• bisect.bisect_right(arr, x): returns the index of the first element that is greater than x. If all elements are ⇐ x, returns len(arr)