参考1 学习基础模版：我作了首诗，保你闭着眼睛也能写对二分查找
参考2 领会二分思路：写对二分查找不是套模板并往里面填空，需要仔细分析题意
参考3 模版：我写了一个套路，助你随心所欲运用二分搜索
二分的本质是「二段性」，并非单调性
- 满足 01 特性（满足/不满足）的「二段性」可以使用二分
- 满足 1? 特性（一定满足/不一定满足）也可以二分
二分查找技巧
- 尽量不要出现 else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节
int mid = left + ((right - left) >> 1);防止溢出- 若排序数组中是无重复元素的，果断用「寻找一个数」的左闭右闭模版
- 实在是颠不对的，有疑惑的地方+1 -1 =，多调试调试，都是玄学
框架
... 标记的部分，就是出现细节问题的地方，是需要重点关注的地方
int binarySearch(vector<int> nums, int target) {
int left = 0, right = ...;
while(...) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
return ...;
}搜索区间
两端都闭 [left, right] 和左闭右开 [left, right) 的区别
- 两端都闭 [2, 3] 会搜索 2,3 [2, 2] 会搜索 2 [3, 2] 时无效跳出循环
- 左闭右开 [2, 3) 会搜索 2 [2, 2] 时无效跳出循环
两端都闭 [left, right] 搜索区间设置方法：
int left = 0;
int right = nums.size() - 1;
while (left <= right) {return mid;}左闭右开 [left, right) 搜索区间设置方法：
int left = 0;
int right = nums.size();
while (left < right) {}
return left;「三分」就是使用两个端点将区间分成三份，然后通过每次否决三分之一的区间来逼近目标值
由于峰顶元素为全局最大值，因此我们可以每次将当前区间分为 [left, mid1]、[mid1, mid2] 和 [mid2, right] 三段
- 如果 arr[mid1] < arr[mid2]，说明峰顶元素不可能存在 [left, mid1] 中，让 left = mid1 + 1
- 如果 arr[mid1] >= arr[mid2]，说明峰顶元素不可能存在 [mid2, right] 中，让 right = mid2 - 1
「二分」和「三分」在渐进复杂度上都是一样的，都可以通过换底公式转化为可忽略的常数，因此两者的复杂度都是 O(logn)
因此选择「二分」还是「三分」取决于要解决的是什么问题：
-
二分通常用来解决单调函数的找 target 问题，但进一步深入我们发现只需要满足「二段性」就能使用「二分」来找分割点；
-
三分则是解决单峰函数 极值问题
因此一般我们将「通过比较两个端点，每次否决 1/3 区间 来解决单峰最值问题」的做法称为「三分」；而不是简单根据单次循环内将区间分为多少份来判定是否为「三分」。
例题：852-[山脉数组-三分极值]-山脉数组的峰顶索引
搜索一个数，如果存在，返回其索引，否则返回 -1
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int binarySearch(vector<int> nums, int target) {
int left = 0;
int right = nums.size() - 1; // 注意
while (left <= right) { // 注意
int mid = left + ((right - left) >> 1);
if (nums[mid] == target) {
return mid;
} else if (target < nums[mid]) {
right = mid - 1; // 注意
} else if (target > nums[mid]) {
left = mid + 1; // 注意
}
}
return -1;
}
int main() {
vector<int> nums = {1, 2, 3, 4, 5};
int idx = binarySearch(nums, 3);
cout << idx << endl; // 2
return 0;
}1、为什么 while 循环的条件中是 <=，而不是 <
因为初始化 right 的为 nums.length - 1，即最后一个元素也要进入循环判断是否是target
所以每次循环的「搜索区间」是「两端都闭区间」 [left, right]
2、什么时候应该停止搜索呢
找到了目标值的时候可以终止，nums[mid] == target
没找到目标值时，如左右边界为 [3, 2]，这时候区间为空，left > right 了，跳出循环
3、为什么是 left = mid + 1，right = mid - 1
else if (target < nums[mid]) {
right = mid - 1; // 注意
} else if (target > nums[mid]) {
left = mid + 1; // 注意
}因为我们的「搜索区间」是[left, right]左闭右闭，当nums[mid]被检测之后，下一步的搜索区间应该去掉mid 分割成两个区间
- 当 target 大于 nums[mid]，由于左边界是闭的，所以 left = mid + 1，
[mid + 1, right] - 当 target 小于 nums[mid]，由于右边界是闭的，所以 right = mid + 1，
[left, mid - 1]
4、该算法有什么缺陷
如果有序数组为 nums = [1,2,2,2,3]，返回的索引为 2，无法得到左右边界
寻找更左侧边界或在左侧位置插入，例如 [1,2,2,3] 找 2 ，下面的算法返回的是 1
即在 idx=1 的位置上插入 2，[1,2,2,2,3]
同时，更左侧位置，也是原数组中与 target 值相同元素们 左边的位置，但前提是target在原数组中
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int lowerBound(vector<int> nums, int target) {
int left = 0;
int right = nums.size(); // 注意
while (left < right) { // 注意
int mid = left + ((right - left) >> 1);
if (nums[mid] == target) {
right = mid;
} else if (target < nums[mid]) {
right = mid; // 注意
} else if (target > nums[mid]) {
left = mid + 1; // 注意
}
}
return left;
}
int main() {
vector<int> nums = {1, 2, 2, 2, 5};
cout << lowerBound(nums, 0) << endl; // 0
cout << lowerBound(nums, 2) << endl; // 1
cout << lowerBound(nums, 3) << endl; // 4
cout << lowerBound(nums, 6) << endl; // 5
return 0;
}1、为什么 while 中是 < 而不是 <=
因为初始化 right 的为 nums.length，所以每次循环的「搜索区间」是「左闭右开」 [left, right)
while(left < right)终止的条件是left == right，此时搜索区间[left, left)为空，所以可以正确终止。
至于为什么 right 要设为为 nums.length 使得「搜索区间」变成「左闭右开」，因为这是绝大数人认可的写法
2、「左侧边界」有什么特殊含义
对于有序数组 nums = [1,2,2,2], target = 2，算法会返回 1，含义是：nums中小于 2 的元素有 1 个
对于有序数组 nums = [2,3,5,7], target = 1，算法会返回 0，含义是：nums中小于 1 的元素有 0 个
对于有序数组 nums = [2,3,5,7], target = 8，算法会返回 4，含义是：nums中小于 8 的元素有 4 个
返回的 idx，其实代表了 target 插在数组中后，左边有几个元素
所以返回值的范围在 [0, nums.size()]
3、为什么该算法能够搜索左侧边界
关键在于对于 nums[mid] == target 这种情况的处理
if (nums[mid] == target)
right = mid;可见，找到 target 时不要立即返回，而是缩小「搜索区间」的上界right，缩小至 mid
在区间[left, mid)中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。
4、为什么右边界的更新变为 right = mid
else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid; // 注意
}因为我们的「搜索区间」是[left, right)左闭右开，当nums[mid]被检测之后，下一步的搜索区间应该去掉mid 分割成两个区间
- 当 target 大于 nums[mid]，由于左边界是闭的，所以还是 left = mid + 1，
[mid + 1, right) - 当 target 小于 nums[mid]，由于右边界是开的，所以 right = mid，
[left, mid)
5、为什么返回left而不是right
都是一样的，因为 while 终止的条件是 left == right
寻找更右侧边界或在右侧位置插入，例如 [1,2,2,3] 找 2 ，下面的算法返回的是 3
即在 idx=3 的位置上插入 2，[1,2,2,2,3]
同时，更右侧位置减一，是原数组中与 target 值相同元素们 右边的位置，但前提是target在原数组中
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int upperBound(vector<int> nums, int target) {
int left = 0;
int right = nums.size(); // 注意
while (left < right) { // 注意
int mid = left + ((right - left) >> 1);
if (nums[mid] == target) {
left = mid + 1; // 注意
} else if (target < nums[mid]) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
return left;
}
int main() {
vector<int> nums = {1, 2, 2, 2, 5};
cout << upperBound(nums, 0) << endl; // 0
cout << upperBound(nums, 2) << endl; // 4
cout << upperBound(nums, 3) << endl; // 4
cout << upperBound(nums, 6) << endl; // 5
return 0;
}1、为什么该算法能够搜索右侧边界
关键在于对于 nums[mid] == target 这种情况的处理
if (nums[mid] == target)
left = mid + 1;找到 target 时不要立即返回，而是缩小「搜索区间」的下界left，缩小至 mid + 1
在区间[left, right)中继续搜索，即不断向右收缩，达到锁定右侧边界的目的。
如果数组为 [1, 2, 2, 4]，长度为 n
使用 lower_bound
| target | 查0 | 查2 | 查3 | 查5 |
|---|---|---|---|---|
| idx | 0 | 1 | 3 | 4 |
| val | 1 | 2 | 4 | NULL |
使用 upper_bound
| target | 查0 | 查2 | 查3 | 查5 |
|---|---|---|---|---|
| idx | 0 | 3 | 3 | 4 |
| val | 1 | 4 | 4 | NULL |
使用 lower_bound 取查一个数或还要用这个值去计算，一定要检查下边界：
- 如果 idx == n，那你可能需要的下标是 idx = n - 1
- 如果 1 <= idx <= n-1
- 如果 nums[idx] == target，那需要的下标就是 idx
- 如果 nums[idx] != target，那需要的下标可能是 idx，也可能是 idx - 1。例如上面数组中查3，可能需要nums[3]=4，也可能是nums[2]=2
- 如果 idx == 0，那可能需要的下标是 idx = 0
代码实现：
int idx = lower_bound(vec.begin(), vec.end(), target) - vec.begin();
if (idx < n) {
使用 vec[idx]; // vec[idx] 大于等于 target
}
if (idx > 0) {
使用 vec[idx-1]; // vec[idx-1] 小于 target
}上面的如果可能有遗漏，但是代码实现没问题
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int leftBound(vector<int> nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
right = mid - 1;
} else if (target < nums[mid]) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
return left;
}
int rightBound(vector<int> nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
return left;
}
int main() {
vector<int> nums = {1, 2, 2, 2, 5};
cout << leftBound(nums, 0) << endl; // 0
cout << leftBound(nums, 2) << endl; // 1
cout << leftBound(nums, 3) << endl; // 4
cout << leftBound(nums, 6) << endl; // 5
cout << rightBound(nums, 0) << endl; // 0
cout << rightBound(nums, 2) << endl; // 4
cout << rightBound(nums, 3) << endl; // 4
cout << rightBound(nums, 6) << endl; // 5
return 0;
}在数组中查找符合条件的元素的下标
| 题目 | 说明 |
|---|---|
| 704. 二分查找 | 二分查找的最原始问题，使用两边夹的二分查找方法需要后处理（退出循环以后，还需要判断 left 或 right 位置的值是不是问题的答案） |
| 35. 搜索插入位置 | lower_bound |
| 34. 在排序数组中查找元素的第一个和最后一个位置 | lower_bound 先找左边届，有左边届的情况下再 upper_bound 找右边届 |
| 611. 有效三角形的个数 | 二分 或 双指针 |
| 4. 寻找两个正序数组的中位数 | 二分查找里最难的问题，重点在于理解：① 为什么是在短数组里找边界；② 深刻理解搜索边界的意义 |
使用二分查找的前提不一定非要是「有序数组」。旋转有序数组（下表前 4 题）、山脉数组（下表后 2 题）里的查找问题也可以使用「二分查找」。这些问题的解决思路是：利用 局部单调性，逐步缩小搜索区间。
| 题目 | 说明 |
|---|---|
| 33. 搜索旋转排序数组 | 旋转有序数组 |
| 81. 搜索旋转排序数组 II | 旋转有序数组 |
| 153. 寻找旋转排序数组中的最小值 | 旋转有序数组 |
| 154. 寻找旋转排序数组中的最小值 II | 旋转有序数组 |
| 162. 寻找峰值 | 山脉数组 |
| 852. 山脉数组的峰顶索引 | 山脉数组 |
| 1095. 山脉数组中查找目标值 | 山脉数组 |
在一个有范围的区间里搜索一个整数
如果题目要我们找一个整数，这个整数有确定的范围，可以通过二分查找逐渐缩小范围，最后逼近到一个数。
定位一个有范围的整数，这件事情也叫「二分答案」或者叫「二分结果」。如果题目要求的是一个整数，这个整数有明确的范围，可以考虑使用二分查找。
事实上，二分答案是我们最早接触的二分查找的场景。「幸运 52」里猜价格游戏，就是「二分查找」算法的典型应用：先随便猜一个数，如果猜中，游戏结束。如果猜大了，往小猜；如果猜小了，往大猜。
| 题目 | 说明 |
|---|---|
| 69. x 的平方根 | 在一个整数范围里查找一个整数，也是二分查找法的应用场景 |
| 287. 寻找重复数 | |
| 374. 猜数字大小 | |
| 275. H 指数 II | 这个问题题解题意得花很多时间，可以跳过不做 |
| 1283. 使结果不超过阈值的最小除数 | |
| 1292. 元素和小于等于阈值的正方形的最大边长 |
每一次缩小区间的时候都需要遍历数组
说明：这一类问题本质上还是「题型二」（二分答案），但是初学的时候会觉得有一些绕。这一类问题的问法都差不多，关键字是「连续」、「正整数」，请大家注意捕捉题目中这样的关键信息。
这里给出的问题解法都一样，会一题等于会其它题。问题的场景会告诉我们：目标变量和另一个变量有相关关系（一般是线性关系），目标变量的性质不好推测，但是另一个变量的性质相对容易推测（满足某种意义上的单调性）。这样的问题的判别函数通常会写成一个函数的形式。
这一类问题可以统称为「 最大值极小化 」问题，最原始的问题场景是木棍切割问题，这道题的原始问题是「力扣」第 410 题（分割数组的最大值（困难））。
思路是这样的：
-
分析出题目要我们找一个整数，这个整数有范围，所以可以用二分查找；
-
分析出 单调性，一般来说是一个变量 a 的值大了，另一个变量 b 的值就变小，而「另一个变量的值」 b 有限制，因此可以通过调整 a 的值达到控制 b 的效果；
-
这一类问题的题目条件一定会给出 连续、正整数 这样的关键字。如果没有，问题场景也一定蕴含了这两个关键信息。
参考资料：
以下给出的问题无一例外。
| 题目 | 说明 |
|---|---|
| 875. 爱吃香蕉的珂珂 | |
| 410. 分割数组的最大值 | |
| LCP 12. 小张刷题计划 | |
| 1011. 在 D 天内送达包裹的能力 | |
| 1482. 制作 m 束花所需的最少天数 | |
| 1552. 两球之间的磁力 |