第 4 节 二分查找模板

• while (left < right) 表示当 left 与 right 重合的时候停止搜索，这样我们就不用思考返回 left 还是 right；
• while 里面只写两个分支，即只有 if 和 else，表示：非此即彼，把其中一种情况考虑好，不满足这种情况的区间就是上一个区间的反面区间。

这一节只需要大家消化一个知识点：只有分成两个区间，退出循环以后，left 和 right 才会重合。

温馨提示：模板代码只是告诉我们所有的二分查找都可以写成以下两种形式。

代码 1：

// 目标元素可能存在在区间 [left..right]
while (left < right) {
    int mid = (left + right) / 2;
    if (判别条件) {
        // 下一轮搜索区间 [mid + 1..right]
        left = mid + 1;
    } else {
        // 下一轮搜索区间 [left..mid]
        right = mid;
    }
}
// 退出循环以后 left == right 成立
// 视情况判断 nums[left] 是否是我们要找的

代码 2：

// 目标元素可能存在在区间 [left..right]
while (left < right) {
    int mid = (left + right + 1) / 2;
    if (判别条件) {
        // 下一轮搜索区间是 [left..mid - 1]
        right = mid - 1;
    } else {
        // 下一轮搜索区间是 [mid..right]
        left = mid;
    }
}
// 退出循环以后 left == right 成立
// 视情况判断 nums[left] 是否是我们要找的

模板代码没有告诉我们：

• 什么时候向左边找、什么时候向右边找；
• 看到的 mid 位置的值是保留还是排除。

这两个问题的答案需要从题目中获得，因此我们必须 认真审题。

为什么二分查找分三种情况讨论的结果需要合并

提示：这里和大家提及一下为什么二分查找虽然可以分三种情况讨论，但是写代码的时候需要合并成两种情况。如果不合并的话，在最后一轮搜索区间只有两个数的时候，如果不合并有可能会造成 left 和 right 在退出以后不能重合。这一点是我 2021 年在「力扣」第 34 题题解区和网友朋友们的讨论得到的。经常和网友讨论问题，会有不少收获。

---

作者：liweiwei1419 链接：https://suanfa8.com/binary-search/template 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。