Binary Search

Template

def binary_search(
        lower_bound: int, 
        upper_bound: int, 
        f: Callabel
    ) -> int:
    left, right = lower_bound, upper_bound

    while left < right:
        mid = (left + right) // 2
        if f(mid):
            right = mid
        else:
            left = mid + 1
    return left

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

Next, we need identify the lower_bound and upper_boundof the search space.

Strategies

  • The problem asks to find minimal/maximal value.

Examples