Binary search is used to do fast search (logarithmic time) on a sorted array. More specifically, you can conduct binary searches on any monotonically increasing/decreasing function. The main idea is to cut the search space in halves repeatedly until the target is found.

Writing binary searches without errors such as off-by-one errors or infinite loops is infamously hard (see quote in first page), and it’s a good idea to stick to one template structure and try to fit the questions into the template.

My personal opinion on the qualities of a good template:

• left and right pointers must define the region of the search space inclusively.
• The search must continue as long as there is a valid search space (while l <= r)
• mid must be calculated as l + ((r - l) // 2) to avoid overflow (not necessary in Python.)
• Solutions must not use left = mid or right = mid to avoid infinite loops. Using left = mid + 1 and right = mid - 1 guarantees the search space always shrinks, avoiding potential infinite loops.

Here is one example template for the classic binary search:

def search(self, nums: List[int], target: int) -> int:
    l, r = 0, len(nums) - 1 

    while l <= r:
        m = (l + r) // 2

        if nums[m] > target:
            r = m - 1
        elif nums[m] < target:
            l = m + 1
        elif nums[m] == target:
            return m
    return -1

Binary search on functions

Most binary search problems boil down to the same structure: you have a search space, and a boolean predicate $f(x)$ that transitions from False to True (or True to False) exactly once across it.

Search space:  [lo .......................... hi]
f(x):           F  F  F  F  F  T  T  T  T  T  T
                               ^
                        you want THIS index

The approach is always the same: define a boolean predicate $f(x)$ for the problem, verify that it’s monotonic (transitions exactly once), and plug it into the template. If you can find the right $f(x)$, the problem is mostly solved.

The predicate is always boolean, but the problem might not present one directly and you’ll construct the predicate yourself. For example, in the Koko Eating Bananas problem, the underlying function is g(x) = hours to eat all bananas at speed x, which returns a number. To quickly find the minimum speed $x$ to eat the bananas under $h$ hours, we can define the predicate f(x) = can she finish at speed x within h hours?, a monotonic True/False predicate we can binary search on.

The Template (find first x where f(x) is True)

This is a template when the function $f(x)$ is monotonically increasing, and we want to find the earliest point where $f(x)$ is True.

Search space:  [lo .......................... hi]
f(x):           F  F  F  F  F  T  T  T  T  T  T
                               ^
                        you want THIS index

def binary_search(lo, hi):
    res = -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if f(mid):       # True — record candidate and search left for earlier points
            res = mid
            hi = mid - 1
        else:            # False — search right
            lo = mid + 1
    return res

The Mirror Template (find last x where f(x) is True)

This is a template when the function $f(x)$ is monotonically decreasing, and we want to find the earliest point where $f(x)$ is True.

Search space:  [lo .......................... hi]
f(x):           T  T  T  T  T  F  F  F  F  F  F
                            ^
                     you want THIS index

def binary_search(lo, hi):
    res = -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if f(mid):       # True — record candidate and search right for later points
            res = mid
            lo = mid + 1
        else:            # False — search left
            hi = mid - 1
    return res

Here are some example questions:

Find Minimum in Rotated Sorted Array 🔗

A rotated sorted array looks like this:

Index:   0  1  2  3  4  5  6
Value:   4  5  6  7  0  1  2
                     ^
               minimum element (rotation point)

We need to find the index of the minimum element. Can we define a monotonic predicate for this? Yes — compare against the last element:

For [4, 5, 6, 7, 0, 1, 2] with nums[-1] = 2:

Index:   0    1    2    3    4    5    6
Value:   4    5    6    7    0    1    2
f(mid):  F    F    F    F    T    T    T
                             ^

It’s monotonic — F F F F T T T. The first True is the minimum.

"""
    Monotonic predicate: f(mid) = nums[mid] <= nums[-1]
    12345 -> TTTTT
    51234 -> FTTTT
    45123 -> FFTTT
    34512 -> FFFTT
    23451 -> FFFFT
"""

class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums)-1
        res = nums[0]
        
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] <= nums[-1]:
                res = nums[mid]
                r = mid - 1
            else:
                l = mid + 1
        return res

• Time Complexity: O(log n)
• Space Complexity: O(1)

Edge case — no rotation: If the array is [1, 2, 3, 4, 5], the predicate is all True, so findMin returns index 0 — the actual minimum. Works correctly.

Search in Rotated Sorted Array 🔗

This is a direct follow-up: once we can find the rotation point (the problem above), we know where the two sorted halves are. We just need to pick the correct half and do a standard binary search in it.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # 1. Find min point of array
        def find_min_idx() -> int:
            l, r = 0, len(nums)-1
            res = 0
            while l <= r:
                mid = (l + r) // 2
                if nums[mid] <= nums[-1]:
                    res = mid
                    r = mid - 1
                else:
                    l = mid + 1
            return res
        min_idx = find_min_idx()

        # 2. Determine the region to do binary search
        if nums[min_idx] <= target <= nums[-1]:
            l, r = min_idx, len(nums) - 1
        else:
            l, r = 0, min_idx

        # 3. Binary search
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1
        return -1

• Time Complexity: O(log n)
• Space Complexity: O(1)

The Same Template Everywhere

The framework generalises to “binary search on the answer” problems — the only difference is what $f(x)$ means:

The pattern is always the same: define a predicate that transitions once (so we have a monotonic function), and binary search for the transition point.