Advanced Binary Search: Rotated Arrays and Result Searching

Three Levels of Binary Thinking

1. Standard Binary Search: Finding an exact value in a sorted data set.
2. Condition-Based Sorting: Finding the boundary point where a Boolean condition flips (e.g., first index where nums[i] >= target).
3. Search on Results (Binary Search on Answer): Bisecting the range of possible answers instead of the input indices.

Rotated Sorted Arrays

When a sorted array is rotated (e.g., [4,5,6,7,0,1,2]), it results in two sorted subarrays. The critical task is determining which half mid belongs to.

Search in Rotated Sorted Array (LeetCode 33)

int search(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 side [left..mid] is sorted
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1; // Target is within this sorted range
            } else {
                left = mid + 1;
            }
        } else { // Right side [mid..right] is sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1; // Target is within this sorted range
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

Find Minimum in Rotated Sorted Array (LeetCode 153)

The minimum element is the transition point where the rotation occurs.

int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        // Compare mid with RIGHT boundary. High -> Low jump happens to the right.
        if (nums[mid] > nums[right]) {
            left = mid + 1; // Minimum must be in the right half
        } else {
            right = mid;    // Minimum could be mid or in the left half
        }
    }
    return nums[left];
}

Binary Search on Answer Space

Prerequisites:

• Possible answers lie within a known range [low, high].
• A monotonic predicate function isValid(x) exists: if isValid(x) is true, then isValid(x+1) (or x-1) is also true.
• The problem asks for a minimum or maximum "limiting value."

Ship Packages Within $D$ Days (LeetCode 1011)

Find minimum capacity: High capacity $\rightarrow$ Few days; Low capacity $\rightarrow$ Many days.

int shipWithinDays(int[] weights, int days) {
    int left = Arrays.stream(weights).max().getAsInt(); // Min capacity must hold heaviest item
    int right = Arrays.stream(weights).sum();            // Max capacity takes everything at once
    
    while (left < right) {
        int midCapacity = left + (right - left) / 2;
        if (canFinish(weights, days, midCapacity)) {
            right = midCapacity; // Valid! Try even smaller capacity
        } else {
            left = midCapacity + 1; // Invalid, must increase capacity
        }
    }
    return left;
}

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

Template Selection Guide