二分法核心及算法细节

本文最后更新于：2022年7月24日下午

核心：

二分并不是仅仅用于找数字的，二分的二，其本质是两种不同的状态，通过每次排除一半来逼近两种状态的分界线。
二分的本质是两段性，并非单调性。只要一段满足某个性质，另外一段不满足某个性质，就可以用二分。

二分细节

注意事项：

所有情况均为if else语句，更加清晰
注意防止mid溢出

普通二分查找

在nums中搜索target，找到返回下标，否则返回-1.

int binarySearch(vector<int> nums, int target) {
    int l = 0;
    int r = nums.size() - 1; // @1
    while(l <= r) // @2
    {
        int m = (r - l) / 2 + l;
        if(nums[m] == target) return m; // 找到元素，返回下标
        else if(nums[m] < target) l = m + 1; // @3
        else if(nums[m] > target) r = m - 1; // @4
    }
    return -1;
}

首先要明确，二分到最后肯定是不断逼近一个数字的，类比数学上二分找函数零点的思想。

上述的四处@，是四个注意的点，下面分别说一下：

@1： r是nums.size()还是nums.size()-1?，这个选择其实是自由的，因为我们二分的目标在于，用尽量少的次数去找到目标值，其本质还是基于遍历的思想（不知道这么说是否准确，我的理解是，二分每次可以舍弃一半，但是这一半的舍弃我们确定不会对结果产生影响，所以舍弃，但是不能舍弃掉未知的元素。举个例子，这个nums数组有n个元素，那就必须n个元素都考虑在内，不能从第2个元素开始遍历）。既然要遍历，那么我们这里的r和l，也就是在确定遍历的范围。我们知道元素的下标是0到nums.size()-1，因此这里选择nums.size()还是nums.size()-1无所谓，只要保证搜索区间范围包含所有元素即可。对于选择nums.size()，那我们的搜索区间就是[l,r)，选择nums.size()-1，我们的搜索区间是[l,r]

@2： l <= r还是l < r，这里的范围是由上面的搜索区间决定的。

如果选择nums.size()，搜索区间是[l,r)，那么这里就应该是l < r，可以用反证法，如果是l <= r，那么如果一直向r逼近的话，r保持不变，l最终等于r，就会越界，所以是l < r。
选择nums.size()-1，我们的搜索区间是[l,r]，这里应该是l <= r，这时不怕越界，如果是l < r的话，l最大也就是r - 1，那么会导致最后一个元素漏掉。
对于最后返回-1，l <= r，终止条件是l 等于 r + 1，区间为空，可直接返回；但如果选择l < r，终止条件是l 等于 r，但可能会漏掉一个元素（之所以可能，是因为如果l等于r等于nums.size()，那么无所谓，但如果是在内部，那么这个地方就没有顾及到）
如果数组是{1, 2, 3, 4, 5, 6, 7}，目标是3，那么就会找不到（已运行验证（注意这里说的是 r=nums.size()并且l < r的循环条件）)，所以为了防止漏掉，要检查这个地方，即

```cpp
if(l < nums.size() && nums[l] == target) return l;
else return -1;


- @3： 3与4是一个问题，放在一块说。有时候是`l = m`，有时候是`l = m + 1`，这里还是由于搜索空间决定的，这里左右边界的变化，决定了下一次的搜索空间。对于这个题，我们要保证所有的都遍历过，而现在`nums[m]`已经遍历过，那么不再需要遍历，下一次的空间就应该是`[l, m - 1]`或者`[m + 1, r]`。这是由一开始的搜索空间决定的，如果一开始是`[l, r)`，那么经过m后，要保持相同格式，就应该是`[l, m)`与
  
  `[m +1, r)`。

### 边界二分查找

上面的二分可以查到目标值，但是如果有多个目标值，我们想要第一个或者最后一个的边界值又该怎么办呢？

要在下一次的**搜索空间**上下功夫：

#### 左边界二分

核心代码：

```cpp
while(l < r) { // 此处同上，由一开始的区间决定，不再解释，不过边界的一般习惯是 <
    int m = (r - l) / 2 + l;
    if(nums[m] == target) {
        r = m; // @1
    } else if(nums[m] > target) {
        r = m; // @2，m已经验证过，但这里保持m，是为了保持[l, r)的区间格式
    } else if(nums[m] < target) {
        l = m + 1; // @3
    }
}
if(l < nums.size() && nums[l] == target) return l; // 原因上面已谈及
else return -1;

@1：当我们找到一个符合条件的，由于需要找最左边的，不能直接返回，而是缩小上界。那如果只出现一次，将其放在r中，但最后返回l，有影响吗？经验证，没有影响，如果只出现一次，在第一次遇见放到r中，那么l会不断逼近直到与r相等（这也就是循环条件），所以最后返回l也是可以的。

右边界二分

核心代码：

while(l < r) { // 此处同上，由一开始的区间决定，不再解释，不过边界的一般习惯是<
    int m = (r - l) / 2 + l;
    if(nums[m] == target) {
        l = m + 1; // @1
    } else if(nums[m] > target) {
        r = m; // 同上
    } else if(nums[m] < target) {
        l = m + 1; // 同上
    }
}
if(l > 0 && nums[l - 1] == target) return l - 1; // @2
else return -1;