AcWing 789. 数的范围 *

Akari2024-01-252024-01-26

[toc]

二分查找（折半查找）之二 | Akari的小站

二分查找 | Akari的小站

AcWing 789. 数的范围 - 糖豆爸爸 - 博客园

AcWing 789. 数的范围 - AcWing - yxc

AcWing 789. 数的范围(二分终极分析！) - AcWing - crayongrq

【A05 二分查找算法最好的板子 - 董晓算法 - 哔哩哔哩】

一杯茶，一包烟，一道算法看一天。

AcWing 789. 数的范围【简单】*

一、题目描述

给定一个按照升序排列的长度为 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

输出样例：

3 4
5 5
-1 -1

二、函数定义与用途

将默认采用升序描述。

1、bsearch_lower

用途：
在升序情况下，返回的是第一个 大于等于 x 的数的位置（下标）
在降序情况下，返回的是第一个 小于等于 x 的数的位置（下标）

2、bsearch_upper

用途：
在升序情况下，返回的是最后一个 大于等于 x 的数的位置（下标）
在降序情况下，返回的是最后一个 小于等于 x 的数的位置（下标）

三、解题方法

这是整数二分的模板题，仔细体会一下模板中的 check() 函数在这里是怎么运用的，以及如果要找的不是上限和下限换成别的情况该如何改动。

1、yxc

或者：

注意：

左闭右闭 [0, n - 1]

数组下标从 0 开始，到 n - 1 结束

默认升序排列
如果是降序，把 bsearch_lower 中的 >= 改为 <=，把 bsearch_upper 中的 <= 改为 >=

bsearch_upper 中，mid = l + (r - l) / 2 + 1：
一个mid = (l + r) >> 1
一个mid = (l + r + 1) >> 1
加不加 1，完全取决于 l = mid 还是 r = mid
l 等于 mid 时必须 +1 向上取整，不然会陷入 l = l 的死循环
r = mid 时候不用加 1，因为下一步 l = r 直接会退出循环

// 寻找大于等于 x 的下限
int bsearch_lower(int l, int r, int x){
    while (l < r){
        int mid = l + (r - l) / 2;
        if (q[mid] >= x) r = mid;   // 降序改为 <=
        else l = mid + 1;
    }
    return l;
}

// 寻找小于等于 x 的上限
int bsearch_upper(int l, int r, int x){
    while (l < r){
        int mid = l + (r - l) / 2 + 1;  // 需要 + 1，防止死循环
        if (q[mid] <= x) l = mid;   // 降序改为 >=
        else r = mid - 1;
    }
    return l;
}

2、糖豆爸爸

跟y总的差不多，只是区间变成了左闭右开。

注意：

左闭右开 [0, n)

数组下标从 0 开始，到 n 结束

默认升序排列
如果是降序，把 bsearch_lower 中的 >= 改为 <=，把 bsearch_upper 中的 <= 改为 >=

int lower_bound(int l, int r, int x) {
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (q[mid] <= x) r = mid;
        else l = mid + 1;
    }
    return l;
}
int upper_bound(int l, int r, int x) {
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (q[mid] < x) r = mid;
        else l = mid + 1;
    }
    return l;
}

3、董晓算法

图中下标是从 1 开始的！而一般都是从 0 开始的！

老实说，我喜欢这种，很容易理解。如图所示：

注意：

左开右开 (-1, n)

数组下标从 -1 开始，到 n 结束

默认升序排列
如果是降序，把 bsearch_lower 中的 >= 改为 <=，把 bsearch_upper 中的 <= 改为 >=

为了方便记忆，可以理解为：
找第一个 >= x 的数，if 中就用 >=
找最后一个 <= x 的数，if 中就用 <=

// 最小化查找（可行区在右侧）：查找第一个 >= x的数的下标
int bsearch_lower(int l, int r, int x){
    while (l + 1 < r){  // l + 1 = r时结束
        int mid = l + (r - l) / 2;
        if (q[mid] >= x) r = mid;
        else l = mid;
    }
    return r;
}

// 最大化查找（可行区在左侧）：查找最后一个 <= x的数的下标
int bsearch_upper(int l, int r, int x){
    while (l + 1 < r){  // l + 1 = r 时结束
        int mid = l + (r - l) / 2;
        if (q[mid] <= x) l = mid;
        else r = mid;
    }
    return l;
}

4、STL 内置方法

lower_bound：

升序：

int p = lower_bound(q, q + n, x) - q;

降序：

int p = lower_bound(q, q + n, x, greater<int>()) - q;

upper_bound：

升序：

int p = upper_bound(q, q + n, x) - q;

降序：

int p = upper_bound(q, q + n, x, greater<int>()) - q;

注意：

左闭右开 [ )

数组下标从 0 开始，到 n 结束

一般来讲,STL 可以处理大于等于，大于，小于等于，小于，一般的数字二分够用

查找左边界，可以直接 lower_bound，如果想要查找右边界，可以使用 upper_bound 然后再减 1。
但是，由于二分不一定是数字二分，有时需要用 check 函数，这里 STL就无法使用 check 函数了，所以，终极解法还是手写二分，容易扩展！

四、AC代码

这两个模板解决的是找 >= || <= || > || < 某个数的最左或最右的位置但这个数不一定在二分的数组中
如果在就能准确找到
如果不在找到的就是最接近答案的数（你要找大于等于5的第一个数）但数组中没有 5 那找到的就是 6 的位置(如果有 6 的话)
所以二分是一定有答案的
我觉得这个二分模板就是解决了我上面说的（>= || <= || > || <）这四种情况

这两个模板是一定有答案的，如果没有答案，那就只能是题目数据里没有，所以才会输出 -1 -1，对应就是代码里的 if 不成立的条件。

1、yxc

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 10;
int n, m, q[N];
int bsearch_lower(int l, int r, int x);
int bsearch_upper(int l, int r, int x);

signed main(void)
{
    scanf("%lld %lld", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%lld", &q[i]);
    while (m--){
        int x;
        scanf("%lld", &x);
        if (x != q[bsearch_lower(0, n - 1, x)]) cout << "-1 -1" << endl;
        else {
            cout << bsearch_lower(0, n - 1, x) << " ";
            cout << bsearch_upper(0, n - 1, x) << endl;
        }
    }
    
    return 0;
}

int bsearch_lower(int l, int r, int x){
    while (l < r){
        int mid = l + (r - l) / 2;
        if (q[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

int bsearch_upper(int l, int r, int x){
    while (l < r){
        int mid = l + (r - l) / 2 + 1;
        if (q[mid] <= x) l = mid;
        else r = mid - 1;
    }
    return l;
}

2、董晓算法

我喜欢这个。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 10;
int n, m, q[N];
int bsearch_lower(int l, int r, int k);
int bsearch_upper(int l, int r, int k);

signed main(void)
{
    scanf("%lld %lld", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%lld", &q[i]);
    while (m--){
        int x;
        scanf("%lld", &x);
        if (q[bsearch_lower(-1, n, x)] != x) cout << "-1 -1" << endl;
        else {
            cout << bsearch_lower(-1, n, x)<< " ";
            cout << bsearch_upper(-1, n, x)<< endl;
        }
    }
    
    return 0;
}

// 最小化查找（可行区在右侧）：查找第一个 >= x的数的下标
int bsearch_lower(int l, int r, int x){
    while (l + 1 < r){      // l + 1 = r时结束
        int mid = l + (r - l) / 2;
        if (x <= q[mid]) r = mid;
        else l = mid;
    }
    return r;
}

// 最大化查找（可行区在左侧）：查找最后一个 <= x的数的下标
int bsearch_upper(int l, int r, int x){
    while (l + 1 < r){      // l + 1 = r 时结束
        int mid = l + (r - l) / 2;
        if (x >= q[mid]) l = mid;
        else r = mid;
    }
    return l;
}

3、糖豆爸爸

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int n, q[N];

// 左闭右开 [ )
int lower_bound(int l, int r, int x) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if (q[mid] >= x)  r = mid;
        else l = mid + 1;
    }
    return l;
}
int upper_bound(int l, int r, int x) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if (q[mid] > x) r = mid;
        else l = mid + 1;
    }
    return l;
}
int main() {
    int T;
    cin >> n >> T;
    for (int i = 0; i < n; i++) cin >> q[i];
    
    while (T--) {
        int x; cin >> x;
        int p = lower_bound(0, n, x); //[0,n)
        if (q[p] != x) {
            puts("-1 -1");
            continue;
        }
        printf("%d ", p);
        p = upper_bound(0, n, x);
        printf("%d\n", p - 1);
    }
    return 0;
}