Binary Search: A Reliable Template and the Mistakes to Avoid

Binary search is easy to understand and surprisingly easy to get wrong. Most bugs come from boundaries: whether the high index is inclusive, and whether to move to mid or mid + 1. Here are two templates you can memorise and apply with confidence.

Template 1: find an exact value

Use this when the array is sorted and you want the index of a target, or -1 if it is missing. Both ends are inclusive.

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Writing lo + (hi - lo) // 2 avoids integer overflow in languages such as Java and C++. In Python it is not required, but it is a good habit.

Template 2: first position that satisfies a condition

Many problems ask for the first index where something becomes true, such as the first element that is at least the target. Here the high end is exclusive.

def lower_bound(nums, target):
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

The result is the insertion point, so it also solves Search Insert Position directly.

Searching on the answer

Binary search is not only for arrays. If you can write a function feasible(x) that is false for small values and true from some point onward, you can binary search the value itself.

Example: Koko Eating Bananas. Given piles and h hours, find the smallest eating speed that finishes in time.

def min_eating_speed(piles, h):
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        hours = sum((p + mid - 1) // mid for p in piles)   # ceil(p / mid)
        if hours <= h:
            hi = mid
        else:
            lo = mid + 1
    return lo

Speed 1 is the slowest and max(piles) is always fast enough, so the answer lies between. Each check costs O(n), and there are O(log m) checks, where m is the largest pile.

Mistakes to avoid

• Mixing the two templates, for example using hi = len(nums) - 1 with while lo < hi.
• Setting lo = mid in a loop that uses floor division, which can cause an infinite loop.
• Forgetting that the data must be sorted, or that the condition must be monotonic.

Time complexity is O(log n) for both templates, and space is O(1).