Binary Search Patterns

Everyone knows binary search finds a value in a sorted array in O(log n). The interview version goes further: searching rotated arrays, finding boundaries, and the powerful binary search on the answer — using binary search over a range of possible answers when the array itself isn't what you're searching.

When to recognize this pattern

• The data is sorted, or has a sorted property you can exploit (rotated, partially sorted).
• You're asked to minimize a maximum or maximize a minimum, or find the smallest value that satisfies a condition — classic "search on the answer."
• A linear scan is too slow and the answer space is monotonic (once a value works, all larger/smaller values work).

The template

This template (lo <= hi, exclusive updates) avoids the off-by-one bugs that sink most binary search attempts:

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2     # avoids overflow in other languages
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Worked examples

Search in rotated sorted array

Problem: A sorted array rotated at an unknown pivot. Find a target in O(log n).

At each step one half is sorted — decide which half could contain the target and recurse into it.

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:           # left half sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                               # right half sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

O(log n). The key is identifying which half is sorted (compare nums[lo] and nums[mid]), then checking if the target lies within that half's range.

Koko eating bananas (binary search on the answer)

Problem: Koko eats k bananas/hour. Given pile sizes and h hours, find the minimum k to finish in time.

The answer (eating speed) is monotonic: if speed k works, any faster speed works. Binary-search k in [1, max(piles)].

import math
def minEatingSpeed(piles, h):
    def hours(k):
        return sum(math.ceil(p / k) for p in piles)
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours(mid) <= h:
            hi = mid            # mid works, try slower
        else:
            lo = mid + 1        # too slow, speed up
    return lo

O(n log(max pile)). This is the high-value pattern: you're not searching the array, you're binary-searching the answer because feasibility is monotonic. Recognizing 'minimize the maximum' framing is the signal.

Find minimum in rotated sorted array

Problem: Find the minimum element of a rotated sorted array in O(log n).

Compare mid to the right end: if nums[mid] > nums[hi], the minimum is to the right; otherwise it's at mid or to the left.

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

O(log n). Comparing to nums[hi] (not nums[lo]) is what makes the boundary logic clean here.

Variations & pitfalls

• Find boundary (leftmost/rightmost occurrence): adjust whether you move on equality — the basis for bisect_left vs bisect_right.
• Search on the answer turns optimization problems ("minimum capacity," "smallest divisor") into feasibility checks — the highest-value variant.
• Pitfall: infinite loops from wrong lo/hi updates. Pick one template (this one) and use it everywhere.

FAQ

What is 'binary search on the answer'?

When you binary-search over the range of possible answers rather than the input array, using a feasibility check. It works when the answer space is monotonic - once a value works, all larger (or smaller) values work. Problems like 'minimum eating speed' or 'minimum capacity to ship in D days' are this pattern.

How do I avoid off-by-one bugs in binary search?

Pick one template and use it everywhere. The lo <= hi loop with lo = mid + 1 and hi = mid - 1 (exclusive updates) is reliable for exact search; the lo < hi with hi = mid form is for boundary/minimum problems. Consistency prevents the infinite loops and off-by-ones that sink most attempts.

How do you binary search a rotated sorted array?

At each step, one half (left or right of mid) is fully sorted - identify which by comparing nums[lo] to nums[mid]. Then check whether the target falls within that sorted half's range; if so search it, otherwise search the other half. Still O(log n).

When can I use binary search if the array isn't sorted?

When the answer space is monotonic even though the input isn't. 'Minimize the maximum' and 'maximize the minimum' problems often qualify: you binary-search the candidate answer and use a feasibility function to decide which way to go.

What's the difference between bisect_left and bisect_right?

bisect_left returns the leftmost position where a value could be inserted (the first occurrence in duplicates); bisect_right returns the rightmost. The difference is whether you move on equality - it's how you find the boundaries of a repeated value.