Backend / Algorithms & data structures / Sorting searching / 01_binary_search_variants.md

Binary search variants

Updated 4 interview angles 5 min read source
On this page8
  1. The canonical version
  2. bisect — Python’s built-in
  3. Pattern: find first / last occurrence of a value
  4. Pattern: search in rotated sorted array
  5. Pattern: binary search on answer
  6. Pattern: median of two sorted arrays
  7. Common bugs
  8. Interview angle

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

python 
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:

python 
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.

python 
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

python 
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

python 
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).

python 
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

python 
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

python 
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 4

  • “When can you binary search something that is not a sorted array?” - whenever there is a monotonic predicate: some P(x) that is false up to a point and true after it. Then you are binary searching for the boundary, and the array is only the most familiar special case.
  • “Give the variants you would expect.” - a rotated sorted array, where one half is always sorted and you decide which to discard; finding a peak by comparing arr[mid] to arr[mid + 1]; integer square root by searching [0, N]; and the k-th smallest across two sorted arrays.
  • “What is ‘binary search on the answer’?” - searching the answer space rather than the input. “What is the smallest capacity that ships everything in D days” has a monotonic feasibility check, so you binary search capacity and call the check at each step. Recognising this turns a hard-looking problem into a standard one.
  • “Where do people go wrong on the mechanics?” - the loop invariant and the boundary. Decide whether the range is inclusive or half-open and keep it consistent, and make sure every branch strictly shrinks the range or it loops forever. Off-by-one here is the most common failure in an otherwise correct solution.