【算法系列02】整数二分怎么玩？

2021年06月01日 23:57 __ _ _ _ _

文章配图

你需要知道，人的事业就如同浪潮，如果你踩到浪头，功名随之而来；而一旦错失，则终其一生都将受困于浅滩与悲哀。

——《洛克菲勒写给儿子的38封信》

文章配图

大家好哇，这里是小编记录算法模板的宝地啦，其中也会包含小编平时学习的一些心得。现在，让我们一起进入算法的世界吧~

本文思路来源于y总~

记得之前学C的时候接触过二分，不过那也是过去式了，现在写还真不一定写得出来。

二分可简单的分为 整数二分和浮点数二分
。如果说二分是否一定能得出结果，除开原题出问题，绝不会有第二种情况。二分是一定能有解的，当然前提得代码正确。

1.整数二分

整数二分更多的是容易出现边界问题，比如一个l到r的区域，在某个点分两边，左边满足其性质，而右边不满足。
这也说明二分实际上是一种边界问题，而不是单调性。 有单调性的一定可以二分，没有单调性的部分问题也是可以二分的，当然具体问题具体分析。
说到边界问题，那么我们平时该如何判断呢？

从下图中可以看到，我们通过分析 确定边界点： 1.如果是 mid=(l+r+1)/2
；再通过if(check(mid))检查，如果是true，则说明答案在区间[mid,r],将mid赋值给l；如果是false，则说明答案在区间[l,mid-1],将mid-1赋值给r。
2.如果是 mid=(l+r)/2
,通过if(check(mid))检查，如果是true，则说明答案在区间[l,mid]，将mid赋值给r；如果是false，则说明答案在区间[mid+1,r]，将mid+1赋值给l。

文章配图

图片：来源于y总
做题时的大致步骤：

确定边界
补充check函数
选择模板

整数二分例题：数的范围

给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入格式

第一行包含整数 n 和 q，表示数组长度和询问个数。

第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。

接下来 q 行，每行包含一个整数 k，表示一个询问元素。

输出格式

共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

数据范围

1≤n≤100000

1≤q≤10000

1≤k≤10000

输入样例：

6 3

1 2 2 3 3 4

输出样例：

3 4

5 5

-1 -1

源代码：

#include<iostream>using namespace std;
const int N = 100010;int n, m;int a[N];
void half(int x) {//函数模板 分两个部分    int r = 0, l = n - 1;    while (r < l) {  //当区间[r,l]被划分为[r,mid]和[mid+1,l]        int mid = l + r >> 1;        if (a[mid] >= x) {  //检查mid是否满足性质            l = mid;        } else {            r = mid + 1;        }    }    if (a[r] != x) {        cout << "-1 -1" << endl;    } else {        cout << r << " ";        r = 0, l = n - 1;        while (r < l) {  //当区间[r,l]被划分为[r,mid-1]和[mid,l]            int mid = l + r + 1 >> 1;            if (r < l) {                if (a[mid] <= x) {  //检查mid是否满足性质                    r = mid;                } else {                    l = mid - 1;                }            }        }        cout << r << endl;    }}
int main() {    cin >> n >> m;    for (int i = 0; i < n; i++) {        cin >> a[i];    }    int x;    //需要查询的数字    while (m--) {    //共m个查询        scanf("%d", &x);        half(x);    }    return 0;}

平时也可多敲敲模板哦！

文章配图