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]

Where o is the unworkable value and x is the workable value. Another variant is when the search space has thing pattern:

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

And the optimization asks to find the maximum value satisfying the condition:

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

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