Binary Search Template

Most Generalized Binary Search

Suppose we have a search space. It could be an array, a range, etc. Usually it’s sorted in ascending order. For most tasks, we can transform the requirement into the following generalized form:

• Minimize $k$ , such that $condition(k)$ $=$ $True$

The following code is the most generalized binary search template:

public class BinarySearchTemplate {
    
    // Define the condition method as per specific problem requirements.
    public static boolean condition(int value) {
        // Placeholder: Implement the actual condition logic
        return false; // Example condition (to be replaced)
    }
 
    public static int binarySearch(int[] arr) {
        // Define the bounds of the search space
        // could be [0, n], [1, n] etc. Depends on problem
        int left = minSearchSpace(arr);
        int right = maxSearchSpace(arr);
 
        // Binary search loop
        while (left < right) {
            int mid = left + (right - left) / 2; // To prevent overflow
            
            if (condition(mid)) {
                right = mid; // Narrow down to left half
            } else {
                left = mid + 1; // Narrow down to right half
            }
        }
        
        // Return the left bound which is the answer
        return left;
    }
}

Tip

What’s really nice of this template is that, for most of the binary search problems,  we only need to modify three parts after copy-pasting this template, and never need to worry about corner cases and bugs in code any more:

• Correctly initialize the boundary variables left and right to specify search space. Only one rule: set up the boundary to include all possible elements;
• Decide return value. Is it return left or return left - 1? Remember this: after exiting the while loop, left is the minimal k​ satisfying the conditionfunction;
• Design the condition function. This is the most difficult and most beautiful part. Needs lots of practice.

Note

What makes binary search work is that there exists a function that can map elements in left half to True, and the other half to False, or vice versa. If we can find such a function, we can apply bs to find the boundary (lower_bound for example)