二分可以解决问题的共同点
数组中存在一条分界线,使得分界线左边的位置都满足某个条件并且右边的位置都不满足同一个条件。
接着我们要找到一条分界线,满足分界线左边的数字都 < x,右边的数字都 >= x
所以现在有一个疑问:分界线怎么找?
一开始,分界线一定是在序列的两个边界,如果数组从1开始存储的话,那么分界线就在0和n + 1的位置;如果数组从0开始存储的话,那么分界线就在-1和n的位置。
两个边界的位置如下图
注意分界线是在两个方框中间的位置,是指向两个元素之间的位置。
如下图
例题:a = {1, 4, 7, 9, 9, 11, 12, 15, 17, 19, 21} 在这个数组中查询小于11的数字有多少个。
步骤分解:
继续循环
到目前为止,分界线还有蓝色竖线画出的三种可能的情况
继续循环
此时分界线还有最后两种可能的情况
继续循环
此时L = 5, R = 6,已经满足循环退出条件L + 1 == R,也就找到了我们的分界线。分界线左边的数字都是 < x 的,右边的数字都是 >= x 的
再来分析一下:
我们看一下[L, R]的中间位置mid = (L + R)/ 2。
如果a[mid] < x
,那么分界线会在M的右边
,否则分界线会在M的左边。
如果a[mid] <= x
, 那么分界线会在M的左边
,否则分界线会在M的右边。
经过不断缩减范围,当L + 1 == R时,我们就找到分界线啦!
思考:
1.最后如果L = 0意味着什么?
答:所有数字都 >= x
2.最后如果L = n意味着什么?
答:所有数字都 < x
代码展示:
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100010;
int n, x;
int a[N];
int main()
{
cin >> n >> x;
for(int i = 1; i <= n; i ++)
{
scanf("%d", &a[i]);
}
int l = 0, r = n + 1;
while(l + 1 < r)
{
int mid = (l + r) / 2;
if(a[mid] < x)
{
l = mid;
}
else r = mid;
}
printf("%d\n", l);
return 0;
}
测试样例
输入数据
11 11
1 4 7 9 9 11 12 15 17 19 21
输出数据
5
来自b站,前来观摩学习
哥们哥们,这个模板确实不用去记+1-1的情况 而且大多数的边界问题处理的都非常好 但是当target 在对应的数组中没有出现的时候这个方法 就会报错了 望补充更新之
哈哈哈这个target如果没有出现的话我之前想到了, 返回之前可以先判断一下
点此查看方法
就是这一段代码, 返回之前先可以先判断一下
哈哈哈那天给忘了更新这个二分的题解了, 今天给更新上
未完待续,明天再来