Binary search variants

Binary search is not just for “find this value in a sorted array.” It’s a fundamental pattern for “find the smallest X satisfying some monotonic predicate.” Most binary search bugs come from off-by-one errors in the boundary handling.

The canonical version

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

Returns index of target, or -1 if not found. Inclusive bounds, lo <= hi.

bisect — Python’s built-in

For most “where does this value go in a sorted array” problems, use the stdlib:

import bisect

bisect.bisect_left(arr, target)   # leftmost insertion point
bisect.bisect_right(arr, target)  # rightmost insertion point (== bisect)
bisect.insort(arr, target)        # insert in sorted order

bisect_left returns i such that arr[i-1] < target <= arr[i]. If target is in arr, this is its first occurrence.

arr = [1, 2, 2, 3, 5]
bisect.bisect_left(arr, 2)    # 1
bisect.bisect_right(arr, 2)   # 3
bisect.bisect_left(arr, 4)    # 4 (where 4 would go)

Pattern: find first / last occurrence of a value

def first_occurrence(arr, target):
    i = bisect.bisect_left(arr, target)
    if i < len(arr) and arr[i] == target:
        return i
    return -1

def last_occurrence(arr, target):
    i = bisect.bisect_right(arr, target) - 1
    if i >= 0 and arr[i] == target:
        return i
    return -1

Pattern: search in rotated sorted array

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

Even when rotated, one half is always sorted. Check which, decide if target lies in it.

Pattern: binary search on answer

When the search space isn’t an array but a range of possible answers — and a predicate P(x) is monotonic (P(x) true → P(x+1) true).

def smallest_x_satisfying(predicate, lo, hi):
    """Find smallest x in [lo, hi] where predicate(x) is True."""
    while lo < hi:
        mid = (lo + hi) // 2
        if predicate(mid):
            hi = mid          # mid might be the answer
        else:
            lo = mid + 1
    return lo if predicate(lo) else -1

This template assumes:

• The answer is in [lo, hi]
• predicate is monotonic in [lo, hi]
• We want the smallest x where it’s True

Example: minimum days to ship within capacity

def ship_within_days(weights, days):
    def can_ship(capacity):
        d = 1; load = 0
        for w in weights:
            if load + w > capacity:
                d += 1; load = 0
            load += w
        return d <= days
    
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_ship(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

We’re searching over capacity values. can_ship(c) is monotonic: bigger capacity → fewer days needed. Binary search finds the smallest capacity where days ≤ target.

Pattern: median of two sorted arrays

def find_median(a, b):
    if len(a) > len(b):
        a, b = b, a    # ensure a is shorter
    n, m = len(a), len(b)
    half = (n + m + 1) // 2
    
    lo, hi = 0, n
    while lo <= hi:
        i = (lo + hi) // 2          # cut in a
        j = half - i                # corresponding cut in b
        
        a_left  = a[i-1] if i > 0 else float("-inf")
        a_right = a[i]   if i < n else float("inf")
        b_left  = b[j-1] if j > 0 else float("-inf")
        b_right = b[j]   if j < m else float("inf")
        
        if a_left <= b_right and b_left <= a_right:
            if (n + m) % 2:
                return max(a_left, b_left)
            return (max(a_left, b_left) + min(a_right, b_right)) / 2
        elif a_left > b_right:
            hi = i - 1
        else:
            lo = i + 1

O(log min(n, m)). The key: cut both arrays so left halves combine to half of total length, then verify the cut is “good.”

Common bugs

• lo + hi overflow — not in Python (arbitrary-precision ints), but in C/Java use lo + (hi - lo) // 2.
• Wrong loop condition — <= vs < depends on whether bounds are inclusive. With inclusive [lo, hi], use <=. With half-open [lo, hi), use <.
• Infinite loops from lo = mid instead of mid + 1 — happens when you lo = mid and mid is calculated by floor division. The pair (lo, hi) = (lo, lo+1) then loops forever.
• Off-by-one returning the answer — after the loop, decide whether lo, hi, or mid is the answer.

Interview angle

• “Binary search a rotated array” — modified version above.
• “Find K-th smallest in two sorted arrays” — binary-search-on-answer or median trick.
• “Find peak element” — binary search comparing arr[mid] to arr[mid+1].
• “Square root of N as integer” — binary search on [0, N].
• “Smallest positive integer X such that P(X) is True for monotonic P” — binary search on answer.