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

写在前面

这里是小飞侠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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

为什么 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;
1
2

但如果没找到，就需要 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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

为什么 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 个 大于 目标元素 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] 是否是我们要找的
1
2
3
4
5
6
7
8
9
10
11
12
13

代码 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] 是否是我们要找的
1
2
3
4
5
6
7
8
9
10
11
12
13

总结

while里面是 l

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

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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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)
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

//当划分成三个区域时， 
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;
    }
  }
1
2
3
4
5
6
7
8
9
10
11