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

By /
⏱ 6 min read

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

See also: Meta Interview Prep

See also: Atlassian Interview Prep

See also: Coinbase Interview Prep

Scroll to Top