Notes on Algorithms

bs

2 min read

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]

When we want to find the maximum value sastifying the condition, the implementation is changed subtlely:

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

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

Graph View

Backlinks