【算法基础】二分查找算法模板

### 整数二分步骤：

1. 找一个区间`[L, R]`，使得答案一定在该区间中
2. 找一个判断条件，使得该判断条件具有二段性，并且答案一定是该二段行的分界点
3. 分析中点`Mid`在该判断条件下是否成立，如果成立，考虑答案在哪个区间；如果不成立，考虑答案在那个区间
4. 如果更新方式写的是`R = Mid`，则不用做任何处理；如果更新方式写的是`L = Mid`，则需要计算`Mid`时加上1

### 分析

二分模板一共有两个，分别适用于不同情况。
算法思路：假设目标值在闭区间`[l, r]`中， 每次将区间长度缩小一半，当`l = r`时，我们就找到了目标值。

![](https://blog.fivk.cn/usr/uploads/2022/02/539890086.png)

二分查找的`ans`分为一下两种：

1. ans在红色区间右端点
2. ans在绿色区间左端点

### 版本1：ans是绿色区间(后半段)的左端点

当我们将区间`[l, r]`划分成`[l, mid]`和`[mid + 1, r]`时，其更新操作是`r = mid`或者`l = mid + 1`，计算`mid`时不需要加1。

###### c++代码模板：

check(mid)返回值：

- true：mid在绿色区域
- false：mid不在绿色区域

```cpp
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}
```

### 版本2：ans是红色区间（前半段）右端点

当我们将区间`[l, r]`划分成`[l, mid - 1]`和`[mid, r]`时，其更新操作是`r = mid - 1`或者`l = mid`;，此时为了防止死循环，计算`mid`时需要加1。

###### c++代码模板：

check(mid)返回值：

- true：mid在红色区域
- false：mid不在红色区域

```cpp
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}
```

为什么需要`+1`？
原因是如果不加上1，那么`mid`得到的是下取整的数，那么有可能`[m,r]`更新过后`m`会一直等于`m`（`m+1==r`的情况）会陷入死循环。

> 对于存在多个重复数，模板一是查找左边界，模板二是查找右边界。
>
> 原理就是这两种情况就是一个是从小到大找，一个是从大到小找。因为二分的前提是要有序嘛～嘿嘿嘿

最后修改：2022 年 02 月 06 日