Binary Search: Variants and Boundary Handling

The Essence of Binary Search

Binary Search is an $O(\log N)$ algorithm that halves the search space at each step. It is applicable to any sorted or monotonic search space.

Crucial Insight: Binary search is not limited to sorted arrays. It applies to any problem where the search space can be partitioned into a "valid" half and an "invalid" half based on a monotonic condition.

Three Classic Templates

Template 1: Finding an Exact Value

Used for finding a target element in a distinct set. Returns -1 if not found.

public int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1; // Closed interval [left, right]
    while (left <= right) {                 // When left == right, range [i, i] still has one element
        int mid = left + (right - left) / 2; // Prevent overflow
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Template 2: Finding the Left Boundary (Lower Bound)

Used for finding the first element that is greater than or equal to ($\ge$) target. Useful for finding the insertion point or the start of a range.

public int lowerBound(int[] nums, int target) {
    int left = 0, right = nums.length; // Range [left, right)
    while (left < right) {             // Exit when left == right
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1; // target is strictly to the right
        } else {
            right = mid;    // nums[mid] >= target, could be the starting point
        }
    }
    return left; // 'left' is the first index where nums[left] >= target
}

Template 3: Finding the Right Boundary (Upper Bound)

Used for finding the last element that is less than or equal to ($\le$) target.

public int upperBound(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid + 1; // Target could be to the right
        } else {
            right = mid;
        }
    }
    return left - 1; // Returns the index of the last element <= target
}

Boundary Consistency Cheat Sheet

Closed Interval [left, right]:
  - Condition: while (left <= right)
  - Shift:     left = mid + 1 / right = mid - 1

Left-closed Right-open [left, right):
  - Condition: while (left < right)
  - Shift:     left = mid + 1 / right = mid

Invariance: Correctness is guaranteed if you ensure the answer must stay within the current [left, right] bounds at every iteration.

Binary Search on Answer Space

When a problem satisfies: "If $x$ is a valid solution, then all values $> x$ (or $< x$) are also valid," we can binary search the answer itself.

Example: Koko Eating Bananas (LeetCode 875)

public int minEatingSpeed(int[] piles, int h) {
    int left = 1, right = Arrays.stream(piles).max().getAsInt();
    while (left < right) {
        int midSpeed = left + (right - left) / 2;
        if (canFinish(piles, midSpeed, h)) {
            right = midSpeed; // Try a slower speed
        } else {
            left = midSpeed + 1; // Must go faster
        }
    }
    return left;
}

private boolean canFinish(int[] piles, int speed, int h) {
    int hoursSpent = 0;
    for (int p : piles) {
        hoursSpent += (p + speed - 1) / speed; // Efficient ceiling division
    }
    return hoursSpent <= h;
}

Binary Search in Rotated Sorted Arrays (LeetCode 33)

The key is identifying which half of the array is "well-sorted" at every mid-point.

public int search(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) return mid;
        
        if (nums[l] <= nums[mid]) { // Left half [l, mid] is sorted
            if (target >= nums[l] && target < nums[mid]) r = mid - 1;
            else l = mid + 1;
        } else { // Right half [mid, r] is sorted
            if (target > nums[mid] && target <= nums[r]) l = mid + 1;
            else r = mid - 1;
        }
    }
    return -1;
}

Precision Handling for Floats

public double mySqrt(double x) {
    double left = 0, right = x;
    // Iterate until the gap is smaller than desired precision
    while (right - left > 1e-7) {
        double mid = (left + right) / 2.0;
        if (mid * mid > x) right = mid;
        else left = mid;
    }
    return left;
}

Common Pitfalls Summary

Applicability Checklist

• Is the search space monotonic or segmented into two halves by a condition?
• Are the limits of the answer range known?
• Can you implement a check(x) function in $O(N)$ or better?
• Are you solving for an exact value or a "boundary" (min/max)?