算法——二分算法

第一步，要判断题目是否具有二分性质。通常会根据二分性质设计一个check函数，有了该函数的返回值就能够很好的控制左右指针的移动。所以，难点在与提取二分性质（暂时没有学会很好的通用方法）。

一般用问题的类型来判断是否使用二分，然后从二分问题的类型来进一步推断二分性质是什么。

常见的二分题型：

二分查找

二分答案：求最小（最小化最大值）、求最大（最大化最小值）

第 $K$ 大、第 $K$ 小

第二步，确定二分模板。注意左右区间的开闭，常用左闭右闭、左开右开。模板之间的转换在下面推导。

二分模板

题目：寻找已排序数组 $n u m s$ 中第一个大于等于指定元素 $t a r g e t$ 的位置。即， $\ge x$ 。

int lowerBound(vector<int>& nums, int target) {
   
    int l = 0, r = nums.size() - 1; // 闭区间[l, r]
    while (l <= r) {
    // 闭区间不为空
        int mid = l + (r - l) / 2; // 防止溢出 int 范围
        if (nums[mid] < target) {
   
            l = mid + 1; // [mid + 1, r]
        } else {
   
            r = mid - 1; // [l, mid - 1]
        }
    }
    // 上述式子确保：
    // nums[l - 1] < target
    // nums[r + 1] >= target
    // 也就是说 [r + 1, n - 1]区间所有元素大于等于 target
    // 则第一个大于等于 target 的元素位置即为 r + 1
    // 根据 while 循环的退出条件有 r + 1 == l
    return l;
}

其他情况可以由该位置推导：

$\Leftrightarrow target \ge (x + 1)$
$\Leftrightarrow (target \ge x) - 1$
$\le x \Leftrightarrow (target \ge (x + 1)) - 1$

// 1. target >= x
int idx = lowerBound(nums, target);

// 2. target > x
int idx = lowerBound(nums, target + 1);

// 3. target < x
int idx = lowerBound(nums, target) - 1;

// 4. target <= x
int idx = lowerBound(nums, target + 1) - 1;

题目

在排序数组中查找元素的第一个和最后一个位置

class Solution {
   
    int lowerBound(vector<int>& nums, int target) {
   
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
   
            int mid = l + (r - l) / 2;
            if (nums[mid] < target) {
   
                l = mid + 1;
            } else {
   
                r = mid - 1;
            }
        }
        return l;
    }
public:
    vector<int> searchRange(vector<int>& nums, int target) {
   
        int l = 0, r = nums.size() - 1;
        int left = lowerBound(nums, target);
        if (left == nums.size() || nums[left] != target) {
   
            return {
   -1, -1};
        }
        int right = lowerBound(nums, target + 1) - 1;
        return {
   left, right};
    }
};

寻找旋转排序数组中的最小值

设每次二分取到的数为 $x = n u m s [mi d]$
如果 $x > n u m s [n - 1]$ ，那么最小值必定在 $[mi d + 1, n - 1]$ ；如果 $x < n u m s [n - 1]$ ，那么最小值必定在 $[0, mi d - 1]$ 。具有二分性质。
由于最小值是必定存在的，所以可以在 $[0, n - 2]$ 进行二分查找，如果 $n u m s [n - 1]$ 是最小值，那么每次 $l$ 会一直左移，直到 $l == n - 1$ 跳出循环，最终答案就是 $n u m s [n - 1]$ 。

class Solution {
   
public:
    int findMin(vector<int>& nums) {
   
        int l = 0, r = nums.size() - 1;
        int end = nums.back();
        while (l <= r) {
   
            int mid = l + (r - l) / 2;
            if (nums[mid] > end) {
   
                l = mid + 1;
            } else {
   
                r = mid - 1;
            }
        }
        return nums[l];
    }
};

搜索旋转排序数组

设 $x = n u m s [mi d]$ 为二分取到的数值， $e n d = n u m s [n - 1]$ 为数组的最后一个数值。用 $x$ 和 $t a r g e t$ 来寻找二分的性质。
讨论 $x$ 在 $t a r g e t$ 右边，或等于 $t a r g e t$ 的情况。其余情况 $x$ 必然在 $t a r g e t$ 左边。
如果 $x > e n d$ ，表示 $x$ 在第一段中，那么 $t a r g e t$ 必定要在第一段中（否则，如果 $t a r g e t$ 在第二段中，那么 $x$ 必然在 $t a r g e t$ 左边，与当前考虑情况矛盾），且 $x$ 必须大于等于 $t a r g e t$ 。
如果 $\le end$ ，说明 $x$ 在第二段中，那么 $t a r g e t$ 可以在第一段，也可以在第二段。
- 如果 $t a r g e t$ 在第一段，那么 $x$ 必然在 $t a r g e t$ 右边
- 如果 $t a r g e t$ 在第二段，那么 $x$ 必须要大于等于 $t a r g e t$ ，才能使得 $x$ 位于 $t a r g e t$ 右边
同样可以在 $[0, n - 2]$ 进行二分查找，如果 $n u m s [n - 1] == t a r g e t$ ，那么 $l$ 也会一直左移直到 $l == n - 1$ 跳出循环，所以只要最后判断 $n u m s [l]$ 是否和 $t a r g e t$ 相等即可。如果相等，则证明找到了；如果不相等，证明没找到。

class Solution {
   
    bool check(vector<int>& nums, int x, int target) {
   
        int end = nums.back();
        if (x > end) {
   
            return target > end && target <= x;
        } else {
   
            return target > end || target <= x;
        }
    }
public:
    int search(vector<int>& nums, int target) {
   
        int l = 0, r = nums.size() - 2;
        while (l <= r) {
   
            int mid = l + (r - l) / 2;
            if (check(nums, nums[mid], target)) {
   
                r = mid - 1;
            } else {
   
                l = mid + 1;
            }
        }
        return nums[l] == target ? l : -1;
    }
};

有序矩阵中第K小的元素

第 $K$ 小问题。
二分性质：对于所有元素都位于 $[minVa l u e, ma x Va l u e]$ ，对于某一个数 $mi d$ 可以统计出小于等于它的数的个数（具体方法参考官方题解），设个数为 $c n t$ 。那么， $mi d$ 越大， $c n t$ 越大； $mi d$ 越小， $c n t$ 越小。所以，二分查找 $mi d$ 的下界，使得 $\ge k$ 。

class Solution {
   
    bool check(vector<vector<int>>& matrix, int k, int mid) {
   
        int n = matrix.size();
        int cnt = 0; // 统计小于等于 mid 的元素个数
        for (int i = 0, j = n - 1; i < n; i ++) {
   
            while (j >= 0 && matrix[i][j] > mid) j --;
            cnt += (j + 1);
        }
        return cnt < k;
    }
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
   
        int n = matrix.size();
        int l = matrix[0][0], r = matrix[n - 1][n - 1];
        while (l <= r) {
   
            int mid = l + (r - l >> 1);
            if (check(matrix, k, mid)) {
   
                l = mid + 1;
            } else {
   
                r = mid - 1;
            }
        }
        return l;
    }
};

在D天内送达包裹的能力

求最小问题。
二分性质：运载能力越大，所用天数越少；运载能力越小，所用天数越多。所以，二分查找运载能力的下界，使得天数符合要求。

class Solution {
   
public:
    int shipWithinDays(vector<int>& weights, int days) {
   
        auto check = [&](int cap) {
   
            int cnt = 1, sum = 0;
            for (int w : weights) {
   
                if (w > cap) return false;
                if (sum + w <= cap) {
   
                    sum += w;
                } else {
   
                    cnt ++;
                    if (cnt > days) {
   
                        return false;
                    }
                    sum = w;
                }
            }
            return true;
        };

        int sum = 0;
        for (int w : weights) sum += w;
        int l = sum / days, r = sum;
        while (l <= r) {
   
            int mid = l + (r - l >> 1);
            if (check(mid)) {
   
                r = mid - 1;
            } else {
   
                l = mid + 1;
            }
        }
        return l;
    }
};