基础算法——二分(与你的女同学玩猜数字游戏)

秋名山码民的主页
欢迎关注点赞收藏⭐️留言
作者水平很有限,如果发现错误,一定要及时告知作者

前言

由于有些读者朋友私聊我,希望出几期基础算法的讲解,kmp,dp,哈希,搜索,贪心等对初学者还是不太友好,所以我打算更新几期基础算法合集,没办法谁让我宠粉丝呢?彦祖,热巴说你呢,快关注!

目录大致如下:

排序(十大排序)——已经讲过
高精度算法
从0->1入门双指针
前缀和
二分
位运算
区间合并

何为二分?

二分,字面意思就是一分为二,就为二分
我们用一个广为流传的故事——猜数字来引入二分

假如,你现在和你的女朋友玩一个游戏,猜数字给定一个范围0-100,你每次进行猜测,女朋友只能告诉你所猜数字是大了,或者是小了,,你根据提示来进行下一步猜想,此刻聪明的彦祖应该会想到当猜50,大了,那你就猜25……反反复复其实这时你就已经用到了二分的思想

都告诉了你们这个游戏,那么我当然会考虑没有女朋友彭于晏的感受了,来教大家用代码实现一下,猜数字游戏,自己与自己玩

#include 
#include 
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

二分:
本质是二分,而不是题目中的单调

基础算法——二分(与你的女同学玩猜数字游戏)_第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 
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;
}


你可能感兴趣的