【LeetCode】一文吃透二分查找（附练习）

二分查找深入浅出，一文吃透！

原文地址：https://github.com/EricPengShuai/Interview/blob/main/algorithm/二分查找.md

0. 引言

1. 基本概念：二分查找就是从一个排好序的序列中查找一个元素，和顺序查找不同的是，二分查找通过逐步缩小搜索区间的方式将搜索范围逐渐缩小，最终定位到我们的目标值或者目标位置，在STL中，lower_bound() 和 upper_bound() 就是利用二分的思想，前者在有序数组中找到第一个大于等于的目标值的位置，后者找到第一个大于目标值的位置
2. 排版说明：
   • 首先是套用模板法，这个很简单，就是记住一个二分查找的模板，然后根据题意套用即可，可以解决99%的问题，但对于个别特殊的问题无法解决，主要参考的是 代码随想录 和 图解二分
   • 其次是直接分析法，这个方法需要忘记所有的模板，没有所谓的「左闭右开」「左闭右闭」的概念，重点是认真理解题意，根据题目的条件分析如何缩减区间，主要参考的是 liweiwei

1. 套用模板法1

首先说明两个概念：

1. 左闭右闭：搜索区间范围是 [left, right]，此时循环条件是left <= right，因为left == right时区间也是存在的

   参考代码：

   int searchInsert(vector<int>& nums, int target) {
     	int n = nums.size();
     	int left = 0;
     	int right = n; // 定义target在左闭右闭的区间里，[left, right]
     	while (left <= right) { 
       		int middle = left + ((right - left) >> 1);
       		if (nums[middle] > target) {
         		right = middle - 1; // target 在左区间，在[left, middle-1]中
       		} else if (nums[middle] < target) {
         		left = middle + 1; // target 在右区间，在[middle+1, right]中
       		} else {
         		return middle; // 数组中找到目标值的情况，直接返回下标
       		}
     	}
     	// 这里需要根据题意分析！！
     	return right+1;
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17

2. 左闭右开：搜索区间范围是 [left, right)，此时循环条件是left < right，因为left == right时区间不存在

   参考代码：

   int searchInsert(vector<int>& nums, int target) {
     	int n = nums.size();
     	int left = 0;
     	int right = n; // 定义target在左闭右开的区间里，[left, right) 
     	while (left < right) {
           int middle = left + ((right - left) >> 1);
       		if (nums[middle] > target) {
         			right = middle; // target 在左区间，在[left, middle)中
       		} else if (nums[middle] < target) {
         		left = middle + 1; // target 在右区间，在 [middle+1, right)中
       		} else {
         		return middle; // 数组中找到目标值的情况，直接返回下标
       		}
     	}
     	// 循环结束时有 right>=left，大多数情况下 left == right，但是为了不越界往往返回right
     	return right;
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17

2. 套用模板法2

统一将判断条件定位 while(left < right)，根据划分区间的不同选择不同的模板

1. 模板一

   将区间 [left, right]划分为分成 [left, mid] 和 [mid + 1, right]，此时计算 mid 不需要 +1

   int bsearch_1(int l, int r)
   {
       while (l < r)
       {
           int mid = (l + r)/2;
           if (check(mid)) r = mid;
           else l = mid + 1;
       }
       return l;
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10

2. 模板二

   将区间 [left, right]划分为分成 [left, mid-1] 和 [mid, right]，此时计算 mid 需要 +1

   int bsearch_2(int l, int r)
   {
       while (l < r)
       {
           int mid = ( l + r + 1 ) /2;
           if (check(mid)) l = mid;
           else r = mid - 1;
       }
       return l;
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10

说明：在大多数情况下，这里使用模板一可以求出左边界，使用模板二可以求出右边界，为什么是大多数情况呢？因为有的题目很特殊需要特别注意判断条件

vector<int> searchRange(vector<int>& nums, int target) {
  if(nums.empty()) return {-1,-1};

  int l = 0, r = nums.size() - 1; //二分范围
  while( l < r)			        //查找元素的开始位置
  {
    int mid = (l + r )/2;
    if(nums[mid] >= target) r = mid;
    else l = mid + 1;
  }
  if( nums[r] != target) return {-1,-1};  //查找失败
  int L = r;
  l = 0, r = nums.size() - 1;     //二分范围
  while( l < r)                   //查找元素的结束位置
  {
    int mid = (l + r + 1)/2;
    if(nums[mid] <= target ) l = mid;
    else r = mid - 1;
  }
  return {L,r};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3. 直接分析法

这里需要忘记前面提到的左闭右闭和左闭右开区间，根据题意分析 right 的初始值，然后分析下一轮的搜索区间是左侧还是右侧

这里根据经验，往往设置的是 while(left < right)，因为只有这样退出循环时才有 left >= right，往往会有 left == right成立， 为了不越界就使用 right 作为目标位置

常见问题

1. 二分查找不一定要求数组有序

力扣上如「山脉数组」「选择有序数组」等可以根据 nums[mid] 的值推测两侧元素的性质，进而缩小搜索区间，这类数组都是接近有序的数组

还有如「寻找重复数」不在输入数组上做二分，而是在输入数组的最小值 min 和最大值 max 组成的连续整数数组上查找一个数，也就是搜索区间是 [min...max]

2. 二分查找取 mid 时何时+1

首先何时+1何时不+1是为了避免死循坏，对于有偶数个元素的区间来说，使用 mid = (left+right)/2 只能取到左边的中位数，如果想要取到右边的中位数就必须+1

再来看为什么有时需要取到右边的首位数，考虑只有两个元素的区间，利用 mid 将区间分为 [left, mid-1] 和 [mid, right]时，如果不+1则无法缩减区间，进而进入死循环

总结

• 写成 while(left < right)，退出循环的时候有 left == right 成立，好处是：不用判断应该返回 left 还是 right；

• 区间 [left..right] 划分只有以下两种情况：

  • 分成 [left..mid] 和 [mid + 1..right]，分别对应 right = mid 和 left = mid + 1；
  • 分成 [left..mid - 1] 和 [mid..right]，分别对应 right = mid - 1 和 left = mid，这种情况下。需要使用 int mid = (left + right + 1) / 2，否则会出现死循环，这一点不用记，出现死循环的时候，把 left 和 right 的值打印出来看一下就很清楚了；

• 退出循环 left == right，如果可以确定区间 [left...right] 一定有解，直接返回 left 就可以，否则还需要对 left 这个位置单独做一次判断；

• 始终保持不变的是：在区间 [left...right] 里查找目标元素。

4. 常见题型

4.1 二分求下标

在给定数组中查找符合条件的元素下标

「选择数组」和「山脉数组」：局部单调性

4.2 二分找答案

在给定的序列中找一个满足条件的答案，通过二分查找逐渐缩小范围，最后逼近到一个数

• 其实按照 liweiwei 的总结还有第三个题型，这里就不继续刷了，先消化消化

5. 总结

其实二分的题目刷多了就有经验了，最主要的分析出二分判断的条件，根据题意判断出是在左区间还是右区间查找元素。另外对于二分意图不明显的题目需要尝试分析出题目的隐藏题意

6. 参考

1. 大部分参考自：写对二分查找不是套模板并往里面填空，需要仔细分析题意
2. 另模板1参考自：代码随想录
3. 另模板2参考自：图解二分