bs

Binary Search

Template

def binary_search(lower: int, upper: int, f: Callable) -> int:
    lo, hi = lower, upper
 
    while lo < hi:
        mi = (lo + hi) // 2
        if f(mi):
            hi = mi
        else:
            lo = mi + 1
    return lo

N.B.: It is almost identical to the bisect_right function from the bisect module. lo is the smallest element satisfying the f condition, i.e., the first x from left to right of the input array:

[o o o o o x x x x x x x]

The most important aspect of binary search problem is to find the monotonic objective encoded in the problem.

Next, we need identify the lower and upper bounds of the search space.

Patterns

• The problem asks to find minimum (or maximum) value.
• The problems requires log(N) time complexity.
• The input is sorted.

Practices

• Minimum Limit of Balls in a Bag
• Find Minimum in Rotated Sorted Array.
• H-Index
• Peak Index in a Mountain Array
• Find K Closest Elements