二分查找的循环不变量全面解析
- 原理
- 二分查找的 bug
- 模版
- 二分法变种
- 寻找左侧/右侧元素的二分查找
- 查找大于 key 的最小值 upper
- 查找小于 key 的最大值 lower
- 大于等于 key 的最小索引 lower_ceil
- 实践
- 69. x 的平方根
- 215. 数组中的第K个最大元素
- 704. 二分查找
- 875. 爱吃香蕉的珂珂
- 1011. 在 D 天内送达包裹的能力
原理
二分查找：相较于顺序查找，二分查找的不是单个元素，而是一个范围。利用数据中的规律不断的将搜索范围减半。
比如，猜数字游戏。
朋友让您在心目中想一个
- Yes
- No
您最多也只要用
第一次只要问朋友是否小于 ，如果TA给出了肯定的答案，说明数字在
类似地，如果TA的回答是否定的，说明对方心目中的数字是在 之间，第二次往大了折半问即可。而后您不断缩小范围，每次减少一半，这样问
次即可，因为
的十次方等于
，大于
。
这就是二分查找。
但是，二分查找有一个问题，就是所有的数据事先要排序，而排序是有成本的。相比查找，排序的速度要慢得多。因此，是否应该对数据先花点时间进行一次排序，则要看具体应用的情况而定。
- 如果只对数据进行一次查找，为此事先进行排序显然就不合算了，只有当查找的次数足够多，通过次数抵消掉它的边际成本，为此花一些时间排序才合算。当然，这个场景有一个前提，就是数据是静态的，比如大学的数据库在进行学籍管理时，每一个年级新生入校后，人员是稳定的，对他们按照学号进行一次排序就有意义。再比如，对于历史数据，比如公司的营收，一旦形成，就是事实，不能修改的，这样做也有意义。
- 在大部分现实生活的应用中，数据总是在变化的，比如一个公司的员工，每个月有新的进来，老的离开。再比如一个人开车时，位置是不断变动的，周围加油站离他的距离也是变化的。在这种情况下，找一个目标是否要对所有的目标先排序，就值得商榷了。
在这种情况下，依然有办法做到利用原来数据有序的特点，动态调整新数据的，让每次排序所做的工作不要太多，需要使用一种叫“堆”的数据结构。
二分查找的 bug
二分查找每次找中间的元素，而算法实现中：
mid = (l + r) / 2; // 可能整型溢出数据规模大概 10 亿级别，就会整型溢出。
mid = l + (r - l) / 2;
模版
递归：
int search(vector<int>& nums, int target) {
return bin_search(nums, 0, nums.size()-1, target);
}
int bin_search(vector<int> nums, int l, int r, int target) {
if( l > r ) return -1;
int mid = l + (r - l) / 2;
if( nums[mid] == target )
return mid;
if( nums[mid] < target )
return bin_search(nums, mid + 1, r, target);
return bin_search(nums, l, mid - 1, target);
}非递归：
/* 二分查找：[low, high] */
int binary_search(int key, int *arr, int len){
// 边界判断，防止翻车
if(len <= 0)
return -1;
int low = 0; // 指向 arr 第一个元素，可改为 size_t 类型
int high = len-1; // 指向 arr 最后一个元素，可改为 size_t 类型
while(low <= high){ // 为什么是 <=，而不是 < ？因为 high 是 len - 1（最后一个元素的索引），属于存在的数
int mid = (low + high) / 2;
// 防止 low + high 溢出的写法，可以换一种写法：生成 low ~ high 之间的数公式 : (high-low+1)+low
// 改成这样：mid = low + (high - low + 1) / 2;
// 主流编译器都会将 /2 转换成位运算 >>1，这是编译器内部的优化。因此我们没有必要手动去做这一步优化，写代码的时候还是写 /2。
// 毕竟，还会产生运算符优先级问题、可读性也会差点。
if(key < arr[mid]) // 小则去前半部分继续查找
high = mid - 1;
else if(key > arr[mid]) // 大则去后半部分继续查找.
low = mid + 1;
else
return mid;
}
return -1;
}- 搜索范围：
- 终止条件：
- 向左查找：
- 向右查找：
一般我们操作数组，也是左闭右开区间。
for( int i = 0; i < len; i++ )
do sth...因为，左闭右开用来表达各种操作和算法的边界会简洁清晰很多
中所有算法的处理多是左闭右开区间
。
除了代码风格外，一般是算法方面的原因。
分治算法，如果一个左闭右开区间 ，子区间可以分解为
，父子同构，天然适合分治实现。
在整数范围内，如果非要写为左闭右闭区间，也是可以的。 分解的子区间为
。
但是无论怎么分，总有一个区间和其他不同，划分偏左或偏右一个元素，划分是不整齐的。要打各种边界处理补丁来弥补。
所以，二分查找还有另外一个变种，用左闭右开的区间来实现。
- 初始条件：
- 终止条件：
- 向左查找：
- 向右查找：
只有加一，没有减一。
#include <iostream>
using namespace std;
template <typename T>
int binary_search_array(const T& key, const T arr[], int N) {
if (N <= 0)
return -1;
int low = 0;
int high = N;
while (low < high) {
int mid = low + (high - low + 1) / 2;
if (key < arr[mid]) // 小则去前半部分继续查找.
high = mid;
else if (key > arr[mid]) // 大则去后半部分继续查找.
low = mid + 1;
else
return mid;
}
return -1;
}
int main() {
int a[5] = {1, 2, 3, 4, 5};
cout << binary_search_array(2, a, 5) << endl;
return 0;
}如果是算法，通常左闭右开都是用迭代器来实现：
// 使用迭代器, 描述更清晰
#include<iostream>
#include<vector>
using namespace std;
template <typename T, typename iterator>
bool binary_search_iterator(const T& key, iterator L, iterator H) {
while (L < H) {
iterator M = L + (H - L + 1) / 2;
if (key < *M) // 小则去前半部分继续查找.
H = M;
else if (*M < key) // 大则去后半部分继续查找.
L = M + 1;
else
return true;
}
return false;
}
int main() {
vector<int> v = {1, 2, 3, 4, 5};
cout << binary_search_iterator(2, v.begin(), v.end()) << endl;
return 0;
}
二分法变种
寻找左侧/右侧元素的二分查找
二分查找还有可能查找到多个 key，但题目只要其中一个。
如有序数组 nums= [1, 3, 3, 3, 4]，target = 3，算法返回的是 2（中间的3），但我们可能要第一个 3、或者最后一个 3（ceil）。
- 第一个值等于 key 的索引
// 查找第一个值等于 key 的索引
int first_equals(int key, int* arr, int N) {
int l = 0, r = N - 1;
while (l < r) {
int mid = l + (r - l) / 2;
// 不加 1（上取整变成下取整），如果加 1 会死锁（一直循环）
// 下取整找不到右边界，上取整找不到左边界，所以如果是查找左边界就是下取整，查找右边界就是上取整
if (arr[mid] < key)
l = mid + 1;
else
r = mid;
}
if (arr[l] == key && (l == 0 || arr[l - 1] < key))
// 结尾做一下处理：第一个值
return l;
return -1;
}
int main() {
int v[] = {1, 2, 2, 4, 5};
cout << first_equals(2, v, 5) << endl;
return 0;
}
- 最后一个值等于 key 的索引
// 查找最后一个值等于 key 的索引
int ceil(int key, int* arr, int N) {
int l = 0, r = N - 1;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (arr[mid] > key)
r = mid - 1;
else
l = mid;
}
if (arr[l] == key && (l == N - 1 || arr[l + 1] > key))
// 结尾做一下处理：最后一个值
return l;
return -1;
}
int main() {
int v[] = {1, 2, 2, 4, 5};
cout << ceil(2, v, 5) << endl;
return 0;
}
- 最后一个小于等于 key 的索引
// 查找最后一个小于等于 key 的索引
int last_less_or_equals(int key, int* arr, int N) {
int l = 0, r = N - 1;
while (l < r) {
int mid = l + (r - l + 1) / 2;
if (arr[mid] > key)
r = mid - 1;
else
l = mid;
}
if (arr[l] <= key && (l == N - 1 || arr[l + 1] > key))
// 结尾做一下处理： 最后一个<=
return l;
return -1;
}
int main() {
int v[] = {1, 2, 2, 4, 5};
cout << last_less_or_equals(2, v, 5) << endl;
return 0;
}
对于这些问题，应该采用左闭右开到区间：while(left < high)。
查找大于 key 的最小值 upper
查找大于 key 的最小值，如 60 及格成绩里最低的分数是多少：
- 搜索范围：
，因为寻找的这个值可能比数组中的数还大，比数组最后一个索引还要靠右，所以 +1
- 终止条件：
- 向左查找：
，因为寻找的这个值可能比当前寻找范围中的数还大，比最后一个索引还要靠右，所以 +1
- 向右查找：
int upper(const T& key, const T arr[], int N) {
if (N <= 0)
return -1;
int low = 0;
int high = N;
while (low < high) { // high=arr.length，所以使用 <
int mid = low + (high - low) / 2;
if (key < arr[mid]){
high = mid;
}else if (key >= arr[mid]){ // 因为不是寻找 target，而是 target 后面的数，所以 >=
low = mid + 1;
}
return low; // low == high
}
查找小于 key 的最大值 lower
查找小于 key 的最大值：
- 搜索范围：
- 终止条件：
- 向左查找：
- 向右查找：
int lower(const T& key, const T arr[], int N) {
if (N <= 0)
return -1;
int low = -1;
int high = N-1;
while (low < high) {
int mid = low + (high - low + 1) / 2;
if (key < arr[mid]){ // 小则去前半部分继续查找.
high = mid - 1;
}else if (key >= arr[mid]){ // 大则去后半部分继续查找.
low = mid;
}
return low;
}lower 表取下界，upper 表取上界，ceil 表示最大索引。
而后，还有三者的结合关系：
- upper：查找大于 key 的最小值；
- upper_ceil：如果数组中存在 key，返回最后一个 key；如果数组中不存在 key，返回 upper；
- upper_floor：如果数组中存在 key，返回第一个 key；如果数组中不存在 key，返回 lower；
- lower：查找小于 key 的最大值；
- lower_ceil：如果数组中存在 key，返回第一个 key；如果数组中不存在 key，返回 upper；
- lower_floor：如果数组中存在 key，返回最后一个 key；如果数组中不存在 key，返回 lower；
- ceil：查找最后一个值等于 key 的索引；
他们都不需要重写代码，只要在俩个基础函数上做一点点添加即可。
大于等于 key 的最小索引 lower_ceil
- 第一个大于等于 key 的索引
如有序数组 nums= [1, 3, 3, 3, 4]，target = 3，算法返回的是 2（中间的3），但我们要第一个 3。
// 查找第一个大于等于 key 的索引
int lower_ceil(int key, int* arr, int N) {
int l = 0, r = N - 1;
while (l < r) {
int mid = l + (r - l) / 2;
// 不加 1（上取整变成下取整），如果加 1 会死锁（一直循环）
// 下取整找不到右边界，上取整找不到左边界，所以如果是查找左边界就是下取整，查找右边界就是上取整
if (arr[mid] < key)
l = mid + 1;
else
r = mid;
}
if (arr[l] >= key && (l == 0 || arr[l - 1] < key))
// 结尾做一下处理：第一个>=
return l;
return -1;
}
int main() {
int v[] = {1, 2, 2, 4, 5};
cout << first_large_or_equals(2, v, 5) << endl;
return 0;
}
实践
算法竞赛，如果缺失关键的知识，对于大多数题目将一筹莫展，毫无思路。
所以，我们学习了二分法的原理，边界处理。
接着，独自面对问题。
此时，就不要直接看各式各样的“标准答案”，看了答案的人难免会产生错觉：哦，这样，懂了。
其实你没懂，等你再拿到给你的新问题时，还是一脸懵。
究其根源是因为有时遇到难题想不明白怎么做就直接翻答案去了，看完，懂了！
这种懂了是一种幻觉，如果您想明白了，也就再不敢走所谓“捷径”了。
如同有时候就因为我们下了决心，做了计划，大脑就会误以为我们已经做过了，行动的张力就被消减了。
Leetcode 上的二分法解决的问题类型，大概有三种：
- 在数组中查找符合条件的元素的索引
问题 | 思路 |
考察二分查找 | |
- 在一个有上下界的区间里搜索一个整数
题目 | 思路 |
- 判别条件是一个函数
题目 | 思路 |
69. x 的平方根
题目：69. x的平方根。
先自己想。
独自面对问题，也有一点解题技巧，方便开展思路。
- 慢下来，是否真的理解问题
用自己的语言重新表达问题，要求解的是什么？已知什么？要满足哪些条件？ - 能否填充信息
以前有木有见过相似或相关的问题？以前用过的方法这次是否适用？
不相似的地方是否可以引入辅助限制？条件有木有用足？
能不能构造应该比现在更简单一点的问题，先解决简单的？
如果微调已知的条件，甚至改变求解目标，能否找到解题线索？ - 总结
绝不能解决完问题就了事，那就浪费了巩固知识和提升技巧的机会。
你再检查一遍论证过程，尝试用另外的方法解题，寻找更明快简捷的方法，还要问，这次的解法能否用来解决其他问题？
用自己的语言重新表达问题，要求解的是什么？已知什么？要满足哪些条件？
要求的是：，也就是求
。
是一个抛物线，大于
着手写代码：
int mySqrt(int x){
// 边界判断
if( x == 0 || x == 1 )
return x;
int low = 0;
int high = x;
while( low <= high ) {
int mid = low + (high - low) / 2;
if( mid * mid > x )
high = mid - 1;
else
low = mid + 1;
}
return high;
}mid * mid 太大了，所以溢出报错（）。
修改后：
int mySqrt(int x){
// 边界判断
if( x == 0 || x == 1 )
return x;
int low = 0;
int high = x;
while( low <= high ) {
int mid = low + (high - low) / 2;
if( mid > x / mid ) // 取 mid 跟 x/mid 进行比较
high = mid - 1;
else
low = mid + 1;
}
return high;
}
215. 数组中的第K个最大元素
题目：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
数据范围：，因此可以想象答案就在以下的数组中：
- int nums[] = {-1E+4, -1E+4 - 1, …, 0, 1, 2, …, 1E+4}
所以，我们初始化左右边界为数据范围，每个循环里，求出中点 mid 并检验猜测 mid 是否满足要求，即数组里是否有至少 K 个元素大于等于mid。
若有，即mid是可能的答案，若无，排除mid。每个循环只需把数组过一次就可以检验了，用时。
int count_greater(int *nums, int numsSize, int target) {
int count = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] >= target)
count++;
}
return count;
}
int findKthLargest(int* nums, int numsSize, int k) {
int left = (int)-1E+4, right = (int)1E+4 + 1;
while (left < right) {
int mid = (left + right) / 2;
if (count_greater(nums, numsSize, mid) >= k)
left = mid + 1;
else
right = mid;
}
return left - 1;
}
704. 二分查找
题目：https://leetcode-cn.com/problems/binary-search/
二分查找的实现。
class Solution {
public:
int search(vector<int>& nums, int target) {
return bin_search(nums, 0, nums.size()-1, target);
}
int bin_search(vector<int> nums, int l, int r, int target) {
if( l > r ) return -1;
int mid = l + (r - l) / 2;
if( nums[mid] == target )
return mid;
if( nums[mid] < target )
return bin_search(nums, mid + 1, r, target);
return bin_search(nums, l, mid - 1, target);
}
};
875. 爱吃香蕉的珂珂
题目：875. 爱吃香蕉的珂珂 。
用自己的语言重新表达问题，要求解的是什么？已知什么？要满足哪些条件？
- 我们要找珂珂在
小时吃掉所有香蕉的最小速度
能不能构造应该比现在更简单一点的问题，先解决简单的？
- 那最笨的就是珂珂吃的特别慢，每小时只吃掉
根香蕉，而后我们逐渐 递增阿珂吃香蕉的速度到
，刚好满足在
这个二分法的判别条件是一个函数。
inline int max(int a, int b){
return a > b ? a : b;
}
// 判别条件是一个函数
bool canEat(int* piles, int pilesSize, int H, int speed) {
int hours = 0;
for(int i=0; i<pilesSize; i++)
hours += ceil(piles[i] * 1.0 / speed);
// ceil 是 double 类型，向上取整，如 ceil(1.1) = 2
return hours > H;
}
int minEatingSpeed(int* piles, int pilesSize, int H) {
int low = 1;
int high = 0;
for(int i=0; i<pilesSize; i++)
high = max(piles[i], high);
while( low < high ) {
int mid = low + (high - low) / 2;
if ( canEat(piles, pilesSize, H, mid) )
low = mid + 1;
else
high = mid;
}
return low;
}去思考二分法的本质，了解其通过收敛来找到目标的内涵，对每一个二分的题目都进行深度剖析，多分析别人的答案。
- 二分法为什么返回的不是
mid，而是low去思考二分法的本质，了解通过收敛来找到目标的确切范围。
对每个题目深入剖析，看看别人的答案，学习背后的思考过程。 - 二分法之外，是否还有其他方法求解
1011. 在 D 天内送达包裹的能力
题目：https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days/
class Solution {
public:
int shipWithinDays(vector<int>& weights, int days) {
// 确定二分查找左右边界
int left = *max_element(weights.begin(), weights.end()); // 货物中最大重量
int right = accumulate(weights.begin(), weights.end(), 0); // 所有货物重量总和
while (left < right) {
int mid = (left + right) / 2;
// need 为需要运送的天数
// cur 为当前这一天已经运送的包裹重量之和
int need = 1, cur = 0;
for (int weight: weights) {
if (cur + weight > mid) {
++need;
cur = 0;
}
cur += weight;
}
if (need <= days) {
right = mid;
}
else {
left = mid + 1;
}
}
return left;
}
};