28. Advanced Binary Search Applications

Binary Search is not just for finding exact matches. It is a powerful tool for finding boundaries and optimizing functions.

1. Finding First/Last Occurrence

If an array has duplicates (e.g., [2, 4, 4, 4, 5]), standard binary search might return any of the 4s. By slightly modifying the comparison logic, we can specifically find the index of the first 4 or the last 4.

2. Searching Rotated Sorted Arrays

Imagine [6, 7, 1, 2, 3, 4, 5]. This array is sorted but rotated. Standard binary search fails. However, since at least one half of the array will always be sorted, we can use binary search by checking which half the pivot (middle element) belongs to and narrowing the search space efficiently (O(log N)).

3. Function Optimization

If a function output is monotonic (always increases or always decreases), binary search can be used to find the minimum input value needed to achieve a target output, drastically reducing the search space.