Binary Search Variations

Binary search is far more than a tool for finding a target in a sorted list; it is a fundamental pattern for efficiently navigating any well-ordered search space. Mastering its variations is essential for coding interviews, where algorithmic creativity is tested, and for solving complex real-world optimization problems where brute force is impossible. These variations teach you to identify monotonic functions within problems, allowing you to apply a $O(\log n)$ solution where a linear scan seems unavoidable.

From Standard Binary Search to Variations

The classic binary search algorithm operates on a sorted array. It repeatedly divides the search interval in half, comparing the middle element to the target and discarding the half where the target cannot lie. The core invariant is a sorted sequence. The standard implementation's subtlety lies in managing the loop condition and index updates to avoid infinite loops. A common robust template uses while (left <= right) and updates mid = left + (right - left) / 2.

However, the true power of binary thinking emerges when the condition for discarding a search half does not rely on simple value comparison, but on a more general monotonic predicate. A predicate is a function that returns true or false. If you can define a condition F(x) such that it is false for some initial values and then becomes true (or vice-versa) as x increases, you have a monotonic predicate. Binary search can then find the first or last point where this condition flips. This conceptual leap is the gateway to all advanced variations.

Key Variations for Sorted Data Structures

Often, sorted arrays contain duplicates, or the target condition is more nuanced than simple equality. These are common interview problems.

Finding the First or Last Occurrence: Instead of stopping at any matching element, you continue the search to find the boundary. To find the first occurrence of target k, when arr[mid] == k, you don't return. Instead, you set right = mid - 1 to continue searching the left half for an earlier occurrence. The loop ends with left pointing to the first index. For the last occurrence, you set left = mid + 1 when you find a match, searching the right half. The final check ensures the index contains k.

Searching in a Rotated Sorted Array: Imagine a sorted array rotated at an unknown pivot (e.g., [4,5,6,7,0,1,2]). The array is not fully sorted, but one half of any chosen mid point will always be sorted. The algorithm first identifies which half (left or right of mid) is properly sorted by comparing arr[left] and arr[mid]. It then checks if the target lies within that sorted half's range. If it does, the search confines to that half; if not, it searches the other, non-sorted half. This cleverly maintains $O(\log n)$ time.

Binary Search on Non-Traditional Domains

The search space isn't always a linear array. The binary search logic applies wherever you can define a sorted property or a monotonic condition over an index or range.

Finding a Peak Element: A peak is an element greater than its neighbors. In an array, you can find a peak in $O(\log n)$ time. Compare arr[mid] to arr[mid+1]. If arr[mid] < arr[mid+1], a peak must exist in the right half because values are rising to the right. Otherwise, a peak exists in the left half. This works even if the array is not sorted, leveraging the local monotonic trend.

Searching a 2D Matrix (Row-wise Sorted): Consider a matrix where each row is sorted left-to-right, and the first integer of each row is greater than the last integer of the previous row. You can treat the entire 2D matrix as one virtual flattened 1D array. The key is mapping the 1D mid index to 2D coordinates: row = mid / n, col = mid % n (where n is columns). Then perform standard binary search on this virtual array. For a more complex variant where only rows and columns are individually sorted, you start from the top-right corner and eliminate an entire row or column at each step, achieving $O(m+n)$.

Binary Search on Answer (The Most Powerful Variation)

This is the pinnacle application: using binary search to solve optimization problems. Instead of searching for a known target in an explicit data structure, you search for the optimal answer within a range of possible answers.

The process is: 1) Identify a search space for the answer (e.g., minimum capacity, maximum distance). 2) Define a predicate function F(x) that returns true if x is a feasible answer (not necessarily optimal). Critically, this predicate must be monotonic: if F(x) is true, then F(y) is true for all y >= x (or vice-versa, depending on the problem). 3) Perform a binary search on the answer range to find the smallest (or largest) x for which F(x) is true.

Example - "Koko Eating Bananas": Find the minimum integer speed k at which Koko can eat all piles of bananas in h hours. The search space for k is from 1 to the maximum pile size. The predicate F(k) is: "Can Koko finish all piles in h hours at speed k?" This is monotonic—if she can finish at speed k, she can definitely finish at any speed k' > k. Binary search finds the smallest k where F(k) is true. The work lies in efficiently writing the F(k) function, which involves summing ceil(pile / k) for all piles.

Common Pitfalls

1. Infinite Loops and Off-by-One Errors: The most common mistake is incorrectly setting left = mid instead of left = mid + 1 (or similar for right). This can cause the loop to stall when left and right are consecutive. Always use a consistent template and test it on a tiny two-element array. The update must shrink the search space.

1. Misapplying the Technique to Non-Monotonic Conditions: Binary search requires a predicate that allows you to definitively discard one half of the search space. If you cannot guarantee that whenever the condition is true at point x, it remains true for all points after x, then binary search will yield incorrect results. Always verify monotonicity before coding.

1. Overcomplicating the Predicate in "Binary Search on Answer": The predicate function F(x) should be a straightforward simulation or calculation based on a proposed answer x. Avoid embedding secondary optimizations or another binary search inside it unless absolutely necessary. Keep F(x) simple and focused on feasibility.

1. Forgetting Edge Cases in Variations: In rotated array search, arrays with no rotation or two elements need careful handling. When finding the first/last occurrence, what if the target is not present? Your final check against arr[left] must handle index bounds and value mismatch. Always test empty input, single element, two elements, and all-targets-equal cases.

Summary

• Binary search's core principle is efficiently halving a search space where a monotonic predicate holds, not just finding a number in a sorted list.
• Critical variations for interviews include finding the first/last occurrence of a target, searching in a rotated sorted array, and locating peak elements in non-sorted arrays.
• The binary search on answer technique is a powerful framework for optimization problems. You binary search over the possible answer range and use a carefully designed feasibility-check function as your predicate.
• Success hinges on correctly managing loop boundaries to avoid infinite loops and on rigorously ensuring the predicate function you design is truly monotonic.
• In coding interviews, clearly articulate the monotonic condition you've identified before diving into implementation. This demonstrates deep understanding beyond memorized code.