二分查找进阶：旋转数组与答案二分

二分的三类思维

1. 标准二分：在有序数组中找值（已讲）
2. 条件二分：「红蓝染色」——用谓词函数把数组分成两段，找分界点
3. 答案二分：不对数据本身二分，而是对可能的答案范围二分

旋转有序数组

数组在某个位置被旋转（如 [4,5,6,7,0,1,2]），左右两段各自有序。关键：判断 mid 在哪一段，才能确定跳向哪一侧。

搜索旋转排序数组（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]) {      // 左半段有序
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;            // target 在左半段
            } else {
                left = mid + 1;
            }
        } else {                            // 右半段有序
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;             // target 在右半段
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

判断哪段有序：比较 nums[left] 和 nums[mid]，因为旋转后只有一段是「左端 ≤ mid」。

寻找旋转排序数组中的最小值（LeetCode 153）

最小值在旋转点，即从右半段开始的位置：

int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[right]) {
            left = mid + 1;    // 最小值在右半段
        } else {
            right = mid;       // 最小值在左半段（包含 mid）
        }
    }
    return nums[left];
}

答案二分（二分答案）

适用条件：

• 答案在某个范围 [lo, hi] 内
• 存在谓词 f(x)：答案 ≥ x 时满足，< x 时不满足（或反过来）
• 即「是否可以在 X 的限制下做成某事」是单调的

在 D 天内送达包裹的能力（LeetCode 1011）

最小船舶容量：容量越大，天数越少。二分容量（答案）找最小满足条件的：

int shipWithinDays(int[] weights, int days) {
    int left = Arrays.stream(weights).max().getAsInt();  // 至少能装最重的
    int right = Arrays.stream(weights).sum();             // 最多一次装完

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canFinish(weights, days, mid)) {
            right = mid;       // 满足条件，尝试更小
        } else {
            left = mid + 1;    // 不满足，需要更大
        }
    }
    return left;
}

boolean canFinish(int[] weights, int days, int capacity) {
    int count = 1, cur = 0;
    for (int w : weights) {
        if (cur + w > capacity) { count++; cur = 0; }
        cur += w;
    }
    return count <= days;
}

爱吃香蕉的珂珂（LeetCode 875）

二分吃香蕉的速度 k：

int minEatingSpeed(int[] piles, int h) {
    int left = 1, right = Arrays.stream(piles).max().getAsInt();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canEatAll(piles, h, mid)) right = mid;
        else left = mid + 1;
    }
    return left;
}

boolean canEatAll(int[] piles, int h, int speed) {
    int hours = 0;
    for (int p : piles) hours += (p + speed - 1) / speed;  // 向上取整
    return hours <= h;
}

分割数组的最大值最小化（LeetCode 410）

把数组分成 m 个子数组，让「各子数组最大值」最小：

int splitArray(int[] nums, int m) {
    int left = Arrays.stream(nums).max().getAsInt();
    int right = Arrays.stream(nums).sum();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canSplit(nums, m, mid)) right = mid;
        else left = mid + 1;
    }
    return left;
}

boolean canSplit(int[] nums, int m, int maxSum) {
    int count = 1, cur = 0;
    for (int n : nums) {
        if (cur + n > maxSum) { count++; cur = 0; }
        cur += n;
    }
    return count <= m;
}

二分模板选择

找「最小的满足条件的 x」：
  → while (left < right)，满足时 right = mid，不满足时 left = mid + 1
  → 最终 left == right 即答案

找「最大的不满足条件的 x」：
  → 同上逻辑，条件取反