Binary Search Variations You'll Actually Use in Interviews

Why Binary Search Trips People Up

Everyone knows the basic idea: cut the search space in half each time. But in interviews, you rarely get a straightforward "find this element in a sorted array." The real challenge is recognizing when binary search applies and choosing the right variant.

Here are the 5 patterns I've seen cover ~90% of binary search interview questions.

Pattern 1: Classic Search

Find an exact value in a sorted array. The baseline.

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

Pattern 2: First/Last Occurrence (Boundary Search)

Find the first position where a condition becomes true. This is the most versatile pattern.

def first_true(arr, condition):
    """Find the first index where condition(arr[i]) is True.
    Assumes arr is partitioned: [False, False, ..., True, True, ...]
    """
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if condition(arr[mid]):
            hi = mid      # mid might be the answer
        else:
            lo = mid + 1  # mid is definitely not
    return lo  # First True position (or len(arr) if all False)

This handles:

• First element ≥ target (bisect_left)
• First element > target (bisect_right)
• Last element ≤ target (transform the condition)

Pattern 3: Search in Rotated Array

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

Pattern 4: Search on Answer (Binary Search on Result)

Instead of searching an array, search the answer space. Classic examples: "minimum capacity to ship packages in D days", "koko eating bananas."

def min_capacity(weights, days):
    """Minimum ship capacity to ship all weights in 'days' days."""
    def can_ship(capacity):
        day_count, current_load = 1, 0
        for w in weights:
            if current_load + w > capacity:
                day_count += 1
                current_load = 0
            current_load += w
        return day_count <= days
    
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_ship(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Pattern 5: Bisect on Floating Point

When the answer is a real number, use a fixed number of iterations instead of integer comparisons.

def sqrt_binary_search(n, precision=1e-9):
    lo, hi = 0, max(1, n)
    for _ in range(100):  # 100 iterations gives ~10^-30 precision
        mid = (lo + hi) / 2
        if mid * mid < n:
            lo = mid
        else:
            hi = mid
    return lo

The Interview Framework

When you see a problem:

1. Is there a sorted structure? → Pattern 1 or 2
2. Is there a monotonic condition? → Pattern 2 (boundary search)
3. "Find minimum/maximum that satisfies..." → Pattern 4 (search on answer)
4. Rotated? Duplicates? → Pattern 3 with modifications
5. Continuous answer space? → Pattern 5

---

Master these five patterns and binary search stops being tricky. It becomes mechanical.