开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【LeetCode】二分基础模板，查找左右边界 -> 正文阅读

[数据结构与算法]【LeetCode】二分基础模板，查找左右边界

二分基础模板，查找左右边界

文章目录

二分基础模板，查找左右边界

写在前面

这里是小飞侠Pan🥳，立志成为一名优秀的前端程序媛！！！

本篇文章同时收录于我的github前端笔记仓库中，持续更新中，欢迎star~

👉https://github.com/mengqiuleo/myNote

左闭右闭区间 [left, right] 模板

var search = function(nums, target) {
    // right是数组最后一个数的下标，num[right]在查找范围内，是左闭右闭区间
    let left = 0, right = nums.length - 1;
    // 当left=right时，由于nums[right]在查找范围内，所以要包括此情况
    while (left <= right) {
        let mid = left + Math.floor((right - left)/2);
        // 如果中间数大于目标值，要把中间数排除查找范围，所以右边界更新为mid-1；如果右边界更新为mid，那中间数还在下次查找范围内
        if (nums[mid] > target) {
            right = mid - 1;  // 去左面闭区间寻找
        } else if (nums[mid] < target) {
            left = mid + 1;   // 去右面闭区间寻找
        } else {
            return mid;
        }
    }
    return -1;
};

为什么 while 循环的条件是 <=，而不是 < ？

答：因为初始化 right 的赋值是 nums.length - 1，即最后一个元素的索引，而不是 nums.length。

在 right 是这样赋值的前提下，<= 相当于两端都是闭区间 [left, right]，< 相当于左闭右开区间 [left, right)，因为索引大小为 nums.length 是越界的。或者带个具体的数字进去 [3, 2]，可见这时候区间为空，因为没有数字既大于等于 3 又小于等于 2 的吧。所以这时候 while 循环终止是正确的，直接返回 -1 即可。

什么时候应该停止搜索呢？

找到了目标值的时候可以终止：

    if(nums[mid] == target)
        return mid;

但如果没找到，就需要 while 循环终止，然后返回 -1。那 while 循环什么时候应该终止？

while(left <= right) 的终止条件是 left == right + 1，写成区间的形式就是 [right + 1, right]

计算 mid 时需要防止溢出

left + ((right -left) >> 1) 其实和 (left + right) / 2 是等价的，这样写的目的一个是为了防止 (left + right) 出现溢出，另外用位运算替代除法提升性能。

left + ((right -left) >> 1) 对于目标区域长度为奇数而言，是处于正中间的，对于长度为偶数而言，是中间偏左的。因此左右边界相遇时，只会是以下两种情况：

left/mid , right ( left, mid 指向同一个数，right 指向它的下一个数) --> 长度为偶数
left/mid/right （ left, mid, right 指向同一个数）–> 长度为奇数

当长度为偶数时，因为 mid 对于长度为偶数的区间总是偏左的，所以当区间长度小于等于 2 时，mid 总是和 left 在同一侧。

左闭右开区间 [left, right) 模板

var search = function(nums, target) {
    // right是数组最后一个数的下标+1，nums[right]不在查找范围内，是左闭右开区间
    let left = 0, right = nums.length;    
    // 当left=right时，由于nums[right]不在查找范围，所以不必包括此情况
    while (left < right) {
        let mid = left + Math.floor((right - left)/2);
        // 如果中间值大于目标值，中间值不应在下次查找的范围内，但中间值的前一个值应在；
        // 由于right本来就不在查找范围内，所以将右边界更新为中间值，如果更新右边界为mid-1则将中间值的前一个值也踢出了下次寻找范围
        if (nums[mid] > target) {
            right = mid;  // 去左区间寻找
        } else if (nums[mid] < target) {
            left = mid + 1;   // 去右区间寻找
        } else {
            return mid;
        }
    }
    return -1;
};

为什么 while 循环的条件是 <=，而不是 < ？

while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的

当left===right时，对于 [left, right)，既然left=right，可是包括left，又不包括right(左闭右开)，有矛盾。

为什么更新为 `right = mid` 而不是 `right = mid - 1`

因为是左闭右开，所以右边的值是无效的(右开)，所以是right = mid

什么时候应该停止搜索呢？

while(left < right) 的终止条件是 left == right，写成区间的形式就是 [right, right]，或者带个具体的数字进去 [2, 2]，这时候区间非空，还有一个数 2，但此时 while 循环终止了。也就是说这区间 [2, 2] 被漏掉了，索引 2 没有被搜索，如果这时候直接返回 -1 就是错误的。

使用 < 的方法，最后退出循环时，left===right，所以我们不用纠结返回left 还是返回 right

模板进阶 --> 把区间分成两个部分(查找左右边界)

把区间分成两个部分，适合用于查找目标值target的左右边界，或者查找第一个大于target的题目。

虽然网上也会有一些查找左右边界的模板，但是刻意的背模板其实并不好，查找目标值target的左右边界其实是一种把区间划分成两个部分的思想。

力扣上典型的题目就是：

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

35. 搜索插入位置

35题其实就是查找第一个大于等于目标元素的位置，也是用把区间划分成两个部分的思想

把区间划分成两个部分的思想:

每一次我们把一定不存在问题答案的区间去掉就可以了。因此我们只需要 把区间分成两个部分。

如果 mid 的左边（或者右边）不存在答案，那么 mid 就是我们要找的问题的答案；
如果 mid 的左边（或者右边）存在答案，那么 mid 不是我们要找的问题的答案。

把区间分成两个部分，去掉一定不存在目标元素的区间，只在有可能存在目标元素的区间里查找。这样当 left 与 right 重合的时候，我们才可以确定找到了目标元素（或者确定搜索区间里不存在目标元素）。

「力扣」第 34 题

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

比如现在，我们需要查找第一个出现4的位置：

如果当前 mid 看到的元素就等于 4，此时不能确定 4 就是数组当中第 1 次出现的位置。如果我们知道 4 的左边没有 4，オ可以确定此时 mid 是「数字 4 第 1 次出现的位置」。但可以确定的是： 4 的右边一定不是「数字 4 第 1 次出现的位置」。所以此时我们就可以把 right = mid，这样就是把右边排除掉了，相当于分成两部分，一部分包含正确答案，另一部分不包含答案。

「力扣」第 35 题

搜索插入位置

输入: [1, 3, 5, 6], 2
输出: 1

题目中因为找不到目标元素，所以需要我们返回第 1 个大于目标元素 2 的下标，因此返回 1。

「查找第 1 次出现的位置」和「查找第一个大于等于 target 的元素的位置」这样的问题，如果根据 mid 位置的值，把待搜索区间分成 3 个部分，不能够确定问题的答案一定在其中某一个区间里，但一定可以确定的是：问题的答案一定不在其中某一个区间里。所以分成两部分：一部分一定包含正确答案，另一部分不包括。

然后一直舍弃不是正确答案的那部分，最后left和right相等，退出循环。

如果在这里不理解也没有关系，当做完力扣34题后，就可以完全清楚了。

left < right 的两种万能模板

while (left < right) 表示当 left 与 right 重合的时候停止搜索，这样我们就不用思考返回 left 还是 right；

while 里面只写两个分支，即只有 if 和 else，表示：非此即彼，把其中一种情况考虑好，不满足这种情况的区间就是上一个区间的反面区间。

代码 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] 是否是我们要找的

总结

while里面是 l<r

①当l = mid时，前面应该是int mid = l + r + 1 >> 1,并且后面是r = mid - 1;
②当r = mid时，前面应该是int mid = l + r >> 1,并且后面是l = mid + 1。

当搜索区间 [left..right] 里只有 2 个元素的时候：

如果划分区间的逻辑是 left = mid + 1; 和 right = mid; 时，while(left < right) 退出循环以后 left == right 成立，此时 mid 中间数正常下取整就好；
如果划分区间的逻辑是 left = mid; 和 right = mid - 1; 时，while(left < right) 退出循环以后 left == right 成立，此时为了避免死循环，mid 中间数需要改成上取整。

注意：

这两种模板，非常适用于判断左右边界的情况，并且退出循环的条件是：left=right，所以我们最后并不需要考虑返回left还是right。

但是最后返回的left(或者right)其实并没有进行验证(因为left=right直接退出循环，这两个值没有进行到while循环中进行计算)，也就是说，我们可能还需要对left进行判断：

最后返回的left，一定是我们求出来的答案，但是不一定是找到的正确答案
找不一定能找到正确答案，求一定能求出来自己的答案

如果不理解，做了题就会明白。

left <= right 与 left < right 的对比

关于这两种模板的不同，我们通过力扣35题：搜索插入位置来演示。

left <= right

当使用小于等于时，退出循环的条件是：首先left和right相遇，计算出mid=left=right，然后执行left=mid+1，此时left就位于right的右边(left=mid+1=right+1)，不符合条件，退出循环。

力扣35题需要我们找到第一个大于等于目标元素的值。

当使用 left <= right 来解题：

var searchInsert = function(nums, target) {
    const n = nums.length;
    let left = 0, right = n - 1, ans = n;
    while (left <= right) {
        let mid = ((right - left) >> 1) + left;
        if (target <= nums[mid]) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
};

上述代码中：声明一个 ans 变量，一定会出现在 if 和 else 分支里的其中一个。

其实这里也是用到了分成两个部分的思想。

题目要我们找的是：第 1 个大于等于 target 的元素的位置，当看到一个元素 nums[mid] 大于等于 target 的时候，nums[mid] 有可能就是我们要找的，所以把 ans 先保存为 mid；
数组的长度 n ，也就是数组的最后一个元素的下一个位置也有可能是答案，所以一开始的时候设置 ans = n；
if 和 else 里面，不管怎么样，left 和 right 的设置都需要 + 1 或者 -1。设置 left = mid + 1，说明下一轮向右边找，设置 right = mid - 1 ，说明下一轮向左边找。这是因为：mid 如果有可能是解的话，因为有了 ans 的设置，一定不会丢失最优解；
当 left == right 重合的时候，left 位置的值还没有看到(还没有被测试过)，所以要继续找下去，因此循环可以继续的条件是 while (left <= right)；
最后返回的是 ans ，不是 left 或者 right 的任何一个。

如果我们希望使用最后返回left或者right，代码可以改成这样：

var searchInsert = function(nums, target) {
    let left = 0,right = nums.length - 1;
    while(left <= right){
        let mid = left + Math.floor((right - left)/2);
        if(nums[mid] > target){
            right = mid - 1;
        }else if(nums[mid] < target){
            left = mid + 1;
        }else{
            return mid;
        }
    }
    return left;//left下标就是它应该插入的位置(或者是right+1)
};

在这里插入图片描述

解释：

在退出循环之前，首先会出现：left=right=mid 的状态。然后执行 left=mid+1，此时left位于right右边，并且left所在的位置就是答案。或者 right+1 的位置是答案
此时 left>right，满足循环退出的条件。

left < right

再次强调本题的题意：我们要找到指定元素的插入位置，那么其实就是找第一个大于等于指定元素的位置，然后将这个元素向右挤，整体向右挪一个位置，给我们的指定元素留出位置，然后将指定元素放上去。

如果使用 left < right，那么我们就可以用将区间划分成两个部分的思想。

一部分区间包含正确答案，另一部分不包含正确答案，并且在每次二分的过程中逐步舍去。

思路：

首先进行特殊判断，如果是插入的元素比最后一个位置还大，进行特殊处理
然后进行while循环：left < right
在if条件中：如果nums[mid] >= target，虽然我们要找的是比目标值大的元素，但是我们希望找到的元素是尽可能小的，根据数组有序，我们应该无限向左逼近，那么此时应该往左边查找，赋值语句应该是right = mid或者right = mid - 1,但是因为我们要找到第一个大于等于目标元素的位置，而且此时mid有可能等于target，所以mid也有可能是答案，所以应该设置成：right = mid
再次解释 right = mid，我们要找到的位置是可以与目标元素target值相等的，根据if中的条件：nums[mid] >= target，如果 nums[mid]=target，并且在mid左边的元素都是比target小的，那么此时mid就是我们要插入的位置，所以 right = mid。
else中的情况如下所述。

情况 1：如果当前 mid 看到的数值严格小于 target，那么 mid 以及 mid 左边的所有元素就一定不是「插入元素的位置」，因此下一轮搜索区间是 [mid + 1…right]，下一轮把 left 移动到 mid + 1 位置，因此设置 left = mid + 1；
情况 2：否则，如果 mid 看到的数值大于等于 target，那么 mid 可能是「插入元素的位置」，mid 的右边一定不存在「插入元素的位置」。如果 mid 的左边不存在「插入元素的位置」，我们才可以说 mid 是「插入元素的位置」。因此下一轮搜索区间是 [left…mid]，下一轮把 right 移动到 mid 位置，因此设置 right = mid。

var searchInsert = function(nums, target) {
  let len = nums.length;
  //特殊判断：如果是插入的元素比最后一个位置还大
  if(nums[len - 1] < target){
    return len;
  }

  let left = 0,right = len - 1;
  while(left < right){
    let mid = left + Math.floor((right - left)/2);
    if(nums[mid] >= target){
      right = mid;
    }else {
      left = mid + 1;
    }
  }
  return left;
};

其实，将区间划分成两个部分的思想也是把代码分成三个部分，然后进行合并。

当划分成两个区域时，才能保证最后退出循环时left=right。

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

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

//当划分成三个区域时， 
while(left < right){
    let mid = left + Math.floor((right - left)/2)
    if(nums[mid] > target){
      right = mid;
    }else if(nums[mid] < target){
      left = mid + 1;
    }else if(nums[mid] === target){
      right = mid;
    }
  }