答案集

往往是求符合一定条件的最大值或最小值，问题具有两段性（一侧可以实现、一侧不可以）

最典型的二段性问题：minmax/maxmin

「使……最大值尽可能小」是二分答案题目常见的问法。

• minmax 最大值最小
• maxmin 最小值最大

则重点考察 check 函数的写法，常见有二分答案与以下几种的组合：

• 循环不变量（loop invariant），是一组在循环体内、每次迭代均保持为真的某种性质，通常被用来证明程序或算法的正确性。
• 贪心策略/线性扫描
• 双指针法
  • 逆向指针
  • 同向指针
  • 滑动窗口
  • Z型遍历
• 广度优先
• 动态规划

循环不变量

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int n = nums1.length, m = nums2.length;
    if (n > m) {
        return findMedianSortedArrays(nums2, nums1);
    }

    int i = searchMax(0, n, (mid) -> {
        int j = (n + m + 1) / 2 - mid;
        return nums1[mid - 1] <= nums2[j];
    });

    int j = (n + m + 1) / 2 - i;
    int left1 = i == 0? Integer.MIN_VALUE: nums1[i - 1];
    int left2 = j == 0? Integer.MIN_VALUE: nums2[j - 1];
    double med1 = Math.max(left1, left2);
    if ((n + m) % 2 == 1) {
        return med1;
    }

    int right1 = i == n? Integer.MAX_VALUE: nums1[i];
    int right2 = j == m? Integer.MAX_VALUE: nums2[j];
    double med2 = Math.min(right1, right2);
    return (med1 + med2) / 2;
}

lc4. 寻找两个正序数组的中位数

线性扫描

双指针法

例题

• 1011.在D天内送达包裹的能力
• 410.分割数组的最大值
• 875.爱吃香蕉的珂珂
• 剑指OfferII 073.狒狒吃香蕉