[AcWing]二分算法

代码已经在 GITHUB 开源，👉点击直达👈。

〇、算法步骤

注意，这里我并没有以闫总的二分算法模板进行讲解（我认为不好，要考虑很多边界问题）。这里讲解的算法原理来自 B 站的视频：二分查找为什么总是写错？。

在我曾经的文章：数组:二分查找里介绍的二分查找算法有局限性。这里要介绍的二分算法核心模型是“红蓝区间（左右区间）”，而不是某个等于目标值的元素值。正因为如此，该二分算法才具有更大的灵活性，才能处理更复杂的问题。相关示意图和算法步骤如下：

建模：划分“红蓝区间”，确定 isBlue 判断条件。
确定要找的目标元素索引是 left 还是 right。
根据算法伪代码实现算法。
后处理（这里有些重要的问题处理）。

算法伪代码：

left = -1, right = N
while left + 1 != right
    mid = (left + right) / 2
    if isBlue(mid)
        left = mid
    else
        right = mid
return left or right

一、算法模板

这里只给出其中一个模板，便于理解上述算法原理的文字内容。

/**
 * @brief 利用二分算法查找非递减数组中第一个 target 出现的位置
 * @param arr 非递减数组
 * @param target 目标元素
 * @return 第一个 target 出现的位置索引
 */
static int binary_search(vector<int>& arr, int target) {
    // 变量初始化
    int left = -1,              // 初始化 left，因为考虑到无“蓝区间”的情况
        right = arr.size();     // 初始化 right，因为考虑到无“红区间”的情况

    // 二分查找
    while (left + 1 != right) {
        int mid = (left + right) / 2;   // 确定二分点（有时候要考虑溢出情况 -> left + (right - left) / 2）

        if (arr[mid] < target) {     // 这里以寻找数组中出现的第一个 target 为例，判断条件为 '< target'
            left = mid;         // 扩展“蓝区间”的右边界（注意结合图看）
        }
        else {
            right = mid;        // 扩展“红区间”的左边界（注意结合图看）
        }
    }

    // 后处理
    if (right == arr.size() || arr[right] != target) {   // 这里以寻找数组中出现的第一个 target 为例，判断条件中的 target 为目标元素的值
        return -1;              // 后处理要考虑未找到情况（判断条件注意索引越界问题）
    }
    else {
        return right;           // 这里以寻找数组中出现的第一个 target 为例，返回值为 'r'
    }
}

二、其他问题

这里着重讲解一下“后处理”中的关于“索引越界问题”。我认为这是这个算法唯一的小缺点，就是这个后处理需要自己多做一点判断。

首先看两个可能的判断条件：

arr[right] != target 或 arr[left] != target，通过判断返回索引对应的元素值是否与目标值相等来判断。
left == -1 || right == arr.size()，通过 left 与 right 的初始值进行判断。

然后来看几个测试样例(以寻找第一个 target 元素为例)：

下面的测试用例通过算法后，left = 0 且 right = 1，这意味着 arr[right] 会越界！可以证明判断条件 arr[right] != target 行不通（类似的在返回 left 的情况下可以推得 arr[left] != target 也行不通）。
"判断条件 1 的驳例"
1
arr = [-1] target = 5
下面的测试用例通过算法后，left = -1 且 right = 0，但是返回值为 -1（应该返回 right）！可以证明判断条件 left == -1 || right == arr.size() 行不通。
"判断条件 2 的驳例"
1
arr = [5] target = 5
下面的测试用例通过算法后，left = 0 且 right = 1，但是返回值为 right（应该返回 -1）！也可以证明判断条件 left == -1 || right == arr.size() 行不通。
"判断条件 2 的驳例"
1
arr = [1, 6] target = 5