Binary Search Patterns and Variants

The Core Strategy

The essence of binary search is eliminating half of the search space at each step, transforming linear $O(N)$ lookups into logarithmic $O(\log N)$ performance.

Prerequisite: The sequence (or the result space) must be sorted or possess a consistent monotonic property.

Standard Binary Search Template

Boundary issues are the most frequent pitfalls. We recommend the closed-interval [left, right] template for clarity.

// Finds target index in a sorted array; returns -1 if not found
int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1; // Search in [left, right]
    while (left <= right) {                 // Continue while interval is non-empty
        int mid = left + (right - left) / 2; // Prevent integer overflow
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1; // Narrow down to the right half
        } else {
            right = mid - 1; // Narrow down to the left half
        }
    }
    return -1;
}

• Why left <= right? The interval [left, right] remains non-empty as long as left <= right. Once left > right, the search ends.
• Why left + (right - left) / 2? If left and right are large, (left + right) can overflow Integer.MAX_VALUE. This subtraction-based logic is mathematically equivalent but safe.

Searching for Boundaries: Leftmost and Rightmost

When an array contains duplicates, standard binary search finds "any" instance. Boundary search finds the "first" or "last" occurrence.

Finding the Leftmost Boundary (First $\ge$ Target)

int searchLeftBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            // Found target! Don't return, keep moving left to find the earliest occurrence
            right = mid - 1; 
        }
    }
    // Final check: 'left' index must be in bounds and point to the target
    if (left >= nums.length || nums[left] != target) return -1;
    return left;
}

Finding the Rightmost Boundary (Last $\le$ Target)

int searchRightBound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            // Found target! Keep moving right to find the latest occurrence
            left = mid + 1;
        }
    }
    if (right < 0 || nums[right] != target) return -1;
    return right;
}

Variant: Rotated Sorted Array

Input: [3, 4, 5, 6, 1, 2] // [1, 2, 3, 4, 5, 6] rotated by 4

Strategy: Determine which half of the current interval is "perfectly sorted" (untouched by the rotation), then decide if the target lies within that sorted range.

int searchRotated(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;

        if (nums[left] <= nums[mid]) { // Left half [left, mid] is sorted
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1; // Target is in the sorted range
            } else {
                left = mid + 1; // Search the right half
            }
        } else { // Right half [mid, right] is sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1; // Target is in the sorted range
            } else {
                right = mid - 1; // Search the left half
            }
        }
    }
    return -1;
}

Variant: Finding a Peak Element

A peak element is an element strictly greater than its neighbors. It doesn't require global sorting—just local monotonicity.

int findPeakElement(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) { // Note: left < right ensures mid + 1 is always in bounds
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[mid + 1]) {
            // Mid is higher than its right neighbor; peak is at 'mid' or to the left
            right = mid; 
        } else {
            // Mid is lower than its right neighbor; must be in an "upward" slope, peak is to the right
            left = mid + 1;
        }
    }
    return left; // left == right points to the peak
}

Application: Binary Search on Result Values

You can binary search for an optimal value within a known range $[min, max]$ if the condition follows a monotonic trend (e.g., if a ship can carry 10 units, it can definitely carry 11).

Problem: Capacity to Ship Packages Within $D$ Days

int shipWithinDays(int[] weights, int days) {
    // Range: Max single weight (can't go smaller) to total sum (1-day shipping)
    int left = Arrays.stream(weights).max().getAsInt();
    int right = Arrays.stream(weights).sum();

    while (left < right) {
        int midCapacity = left + (right - left) / 2;
        if (canShip(weights, days, midCapacity)) {
            right = midCapacity; // This capacity works, let's try a smaller one
        } else {
            left = midCapacity + 1; // Too slow, must increase capacity
        }
    }
    return left;
}

private boolean canShip(int[] weights, int days, int capacity) {
    int daysNeeded = 1, currentWeight = 0;
    for (int w : weights) {
        if (currentWeight + w > capacity) {
            daysNeeded++;
            currentWeight = 0;
        }
        currentWeight += w;
    }
    return daysNeeded <= days;
}

Summary Checklist

Binary search goes beyond "finding a number in an array." It is a tool to eliminate half of the possibilities based on a property.

• Standard Case: Use while (left <= right) with mid - 1 and mid + 1.
• Boundary Search: Shrink the range in the desired direction instead of returning early.
• Answer Search: Ensure the check(x) function is $O(N)$ or better.
• Prevent Overflow: Always use left + (right - left) / 2.