Advanced Binary Search Interview Patterns: Search Space Reduction and Parametric Search (2025)

Binary Search Beyond Sorted Arrays

Binary search is not just for sorted arrays. The generalized binary search applies to any monotone predicate: if a function f(x) transitions from False to True (or True to False) exactly once over a search space, binary search finds the transition point in O(log n). The template: maintain lo and hi; compute mid; evaluate f(mid); narrow the range. This pattern solves problems that don’t involve arrays at all — binary search over the answer space, binary search over time, binary search over abstract orderings. Mastering this template covers 80% of binary search interview problems.

Template: Binary Search on Answer

Instead of searching for a value in an array, search for the smallest/largest value satisfying a condition. “Find the minimum speed such that you can eat all bananas in h hours” (LC 875). “Find the minimum days to make m bouquets” (LC 1482). Template: binary search over the answer space [lo, hi]; for each mid, check if the condition is satisfiable.

def binary_search_answer(lo, hi, feasible):
    # Find smallest x in [lo, hi] such that feasible(x) is True
    # Assumes: feasible is monotone (False...False...True...True)
    result = hi
    while lo <= hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            result = mid
            hi = mid - 1  # try to find smaller
        else:
            lo = mid + 1
    return result

# Example: Koko eating bananas (LC 875)
def min_eating_speed(piles, h):
    def feasible(speed):
        return sum((p + speed - 1) // speed for p in piles) <= h
    return binary_search_answer(1, max(piles), feasible)

Key: identify the search space [lo, hi] and define a boolean feasible(mid) that is monotone (once it becomes True, it stays True). lo = minimum possible answer, hi = maximum possible answer.

Binary Search on Rotated Arrays

A sorted array rotated at some pivot: [4,5,6,7,0,1,2]. Binary search still works — identify which half is sorted, determine if the target is in the sorted half, recurse accordingly.

def search_rotated(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 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

Find First and Last Position (LC 34)

Find the leftmost and rightmost occurrence of a target. Two binary searches: one for the left boundary, one for the right. Left boundary: when nums[mid] == target, record mid and continue searching left (hi = mid – 1). This finds the first occurrence. Right boundary: when nums[mid] == target, record mid and continue searching right (lo = mid + 1). Alternatively: use bisect_left and bisect_right from Python’s bisect module. bisect_left returns the leftmost position where target can be inserted (= first occurrence if it exists). bisect_right returns the rightmost position. Check if target exists: nums[bisect_left(nums, target)] == target.

def search_range(nums, target):
    def find_left():
        lo, hi, res = 0, len(nums)-1, -1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target: res = mid; hi = mid - 1
            elif nums[mid] < target: lo = mid + 1
            else: hi = mid - 1
        return res
    def find_right():
        lo, hi, res = 0, len(nums)-1, -1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target: res = mid; lo = mid + 1
            elif nums[mid] < target: lo = mid + 1
            else: hi = mid - 1
        return res
    return [find_left(), find_right()]

Median of Two Sorted Arrays and 2D Search

Median of Two Sorted Arrays (LC 4): O(log(min(m,n))) binary search on the smaller array. Binary search on the partition point of the smaller array: ensure the left half of both arrays combined has the correct size. The partition is valid when max(left_A, left_B) ≤ min(right_A, right_B). 2D binary search: Search a 2D matrix where each row and column is sorted (LC 240). Start at the top-right corner. If matrix[r][c] == target: found. If > target: move left (c–). If < target: move down (r++). O(m+n). This works because moving left eliminates the current column; moving down eliminates the current row.

{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is parametric binary search and when do you use it?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Parametric binary search (binary search on the answer) applies when you can define a monotone feasibility function: feasible(x) is False for all x < answer and True for all x >= answer (or vice versa). Instead of searching a sorted array, you search the answer space [lo, hi]. For each midpoint, check feasibility in O(n) or O(n log n). Total complexity: O(n log(hi-lo)). Used when the problem asks for minimum/maximum value satisfying a condition.”}},{“@type”:”Question”,”name”:”How do you avoid off-by-one errors in binary search?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use the invariant: at every step, the answer is in [lo, hi]. Compute mid = lo + (hi – lo) // 2 (avoids integer overflow). When feasible(mid) is True, record mid and search left (hi = mid – 1) for the minimum, or search right (lo = mid + 1) for the maximum. When False, narrow away from mid. The loop ends when lo > hi; the recorded result is the answer. Consistency: always move lo past mid or hi below mid to guarantee termination.”}},{“@type”:”Question”,”name”:”How does binary search work on a rotated sorted array?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”At each step, determine which half is sorted (compare nums[lo] to nums[mid]). If nums[lo] <= nums[mid], the left half is sorted — check if the target is within [nums[lo], nums[mid]). If yes, narrow to the left; otherwise, narrow to the right. If nums[lo] > nums[mid], the right half is sorted — check if the target is within (nums[mid], nums[hi]]. The key insight is that exactly one half is always sorted in a rotated array.”}},{“@type”:”Question”,”name”:”How do you find the median of two sorted arrays in O(log(min(m,n)))?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Binary search on the partition point of the smaller array. For a partition at index i in array A and j in array B (where i+j = (m+n+1)//2), the partition is valid when max(A[i-1], B[j-1]) <= min(A[i], B[j]). If A[i-1] > B[j]: move partition left (hi = i-1). If B[j-1] > A[i]: move partition right (lo = i+1). The median is the average of max(left halves) and min(right halves) for even-length, or max(left halves) for odd-length.”}},{“@type”:”Question”,”name”:”How do you search in a 2D matrix where rows and columns are sorted (LC 240)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Start at the top-right corner (row 0, last column). At each step: if the value equals the target, return found. If the value is greater than the target, move left (this column's remaining values are too large). If the value is less, move down (this row's remaining values are too small). Each step eliminates an entire row or column. O(m+n) time. This works because the top-right is the unique position where you can make a definitive binary decision based on whether to go left or down.”}}]}