二分查找的循环不变量全面解析
- 原理
- 二分查找的 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;
}
};