基础算法——二分（与你的女同学玩猜数字游戏）
秋名山码民的主页 🎉欢迎关注🔎点赞👍收藏⭐️留言📝 🙏作者水平很有限，如果发现错误，一定要及时告知作者
前言
由于有些读者朋友私聊我，希望出几期基础算法的讲解，kmp，dp，哈希，搜索，贪心等对初学者还是不太友好，所以我打算更新几期基础算法合集，没办法谁让我宠粉丝呢？彦祖，热巴说你呢，快关注！
目录大致如下：
排序（十大排序）——已经讲过 高精度算法 从0->1入门双指针 前缀和 二分 位运算 区间合并
何为二分？
二分，字面意思就是一分为二，就为二分 我们用一个广为流传的故事——猜数字来引入二分
假如，你现在和你的女朋友玩一个游戏，猜数字给定一个范围0-100，你每次进行猜测，女朋友只能告诉你所猜数字是大了，或者是小了，，你根据提示来进行下一步猜想，此刻聪明的彦祖应该会想到当猜50，大了，那你就猜25……反反复复其实这时你就已经用到了二分的思想
都告诉了你们这个游戏，那么我当然会考虑没有女朋友彭于晏的感受了，来教大家用代码实现一下，猜数字游戏，自己与自己玩
#include <iostream>
#include <cstdlib>
using namespace std;
int main()
{
int a = rand() % 100;
cout << "请猜想你的数字" << endl;
while (1) {
int q;
cin >> q;
if (q > a) {
cout << "大了" << endl;
}
else if (q < a) {
cout << "小了" << endl;
}
else {
cout << "恭喜猜对了" << endl;
break;
}
}
return 0;
}当然如果你们心有灵犀也不排除不用二分一次就对的情况，但是二分绝对是较优的解法。
例题
经过上面的那个小游戏，相信大家对二分也有了一个初步的了解，下面我们再通过一个二分的模板例题来加深印象
给定一个升序排列的长度为n的整数数组，以及q个查询 对于每一个查询，返回一个元素k的起始位置和终止位置 如果不存在则返回-1
二分： 本质是二分，而不是题目中的单调
当想找不满足性质的边界值（棕色区域的右边界值）
- 找中间值 mid = (l+r+1)/2
- if(check(mid))等于true或者是false check(m)是检查m是在不满足性质的区间（检查是不是在棕色区间）
- 更新l或者r
当想找满足性质的边界值（红色区域的左边界值）
- 找中间值 mid = (l+r+1)/2
- if(check(mid))等于true或者是false check(m)是检查m是在满足性质的区间（检查是不是在红色区间）
- 更新l或者r
先写一个check函数 判定在check的情况下（true和false的情况下），如何更新区间。 在check(m)==true的分支下是: l=mid的情况，中间点的更新方式是m=(l+r+1)/2 r=mid的情况，中间点的更新方式是m=(l+r)/2
保证l=r，搜索最后的答案是闭区间的
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int n, q, k;
int a[maxn];
int main() {
#ifndef judge
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
scanf("%d%d", &n, &q);
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
for (int i = 0; i < q; i++) {
scanf("%d", &k);
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (a[mid] >= k) {
r = mid; //第二种情况 找绿色区间的左端点
} else {
l = mid + 1;
}
}
if (a[l] != k) {
printf("-1 -1\n");
} else {
printf("%d ", l);
l = 0, r = n - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (a[mid] <= k) {//第一种情况 找红色区间的右端点
l = mid;
} else {
r = mid - 1;
}
}
printf("%d\n",l);
}
}
return 0;
}
腾讯云开发者
