二分查找模板题（数的范围）题解

这是一题非常典型的二分查找数据左下界和右上界模板题。

题目

题目链接

AcWing的网站，https://www.acwing.com/solution/acwing/content/3338/。

题目描述

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

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

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

输入格式

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

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

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

输出格式

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

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

样例输入

6 3
1 2 2 3 3 4
3
4
5
           

样例输出

3 4
5 5
-1 -1
           

数据范围

1 ≤ n ≤ 100000

1 ≤ q ≤10000

1 ≤ k ≤ 10000

分析

本题是一个标准的二分查找模板题，查找某个数的左边界和右边界。

使用 STL

使用 STL 的 lower_bound() 和 upper_bound() 函数的时候，有以下几个地方需要特别注意：

1、函数的返回值是一个左闭右开的区间。

2、使用 lower_bound() 查找左下界的时候，要注意处理没有找到的情况。比如有这样的数列 [3 5 5 8 7 7 9 10 11]，我们要查找 4，得到的位置将是数列中 3 所在位置。

3、使用 upper_bound() 查找右上界的时候，要注意返回值是左闭右开区间，意味着比实际值大一。

lower_bound

该函数介绍请参考https://blog.csdn.net/justidle/article/details/104346825。

upper_bound

该函数介绍请参考https://blog.csdn.net/justidle/article/details/104346950。

AC 参考代码

#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

const int MAXN = 1e5+6;
int a[MAXN];

int main() {
    int n, q;
    scanf("%d%d", &n, &q);

    int i;
    for (i=0; i<n; i++) {
        scanf("%d", &a[i]);
    }

    for (i=0; i<q; i++) {
        int k;
        scanf("%d", &k);

        int pos1 = lower_bound(a, a+n, k)-a;
        int pos2 = upper_bound(a, a+n, k)-a-1;
        if (k!=a[pos1]) {
            printf("-1 -1\n");
        } else {
            printf("%d %d\n", pos1, pos2);
        }
    }

    return 0;
}
           

注意

1、上面代码如何判断数据 k 不存在，即使用 k!=a[pos1] 来判断。

2、使用 upper_bound 需要多减 1，因为返回的是左闭右开区间，也就是不包含右边点。

自己实现函数

查找左边界

这部分模板代码请参考https://blog.csdn.net/justidle/article/details/104304725。

查找右边界

这部分模板代码请参考https://blog.csdn.net/justidle/article/details/104304742。

AC 参考代码

#include <cstdio>
using namespace std;

const int MAXN = 1e5+6;
int a[MAXN] = {};

int main() {
    int n, q;
    scanf("%d%d", &n, &q);

    int i;
    for (i=0; i<n; i++) {
        scanf("%d", &a[i]);
    }

    for (i=0; i<q; i++) {
        int k;
        scanf("%d", &k);

        //从0~n-1找左边界
        int left = 0;
        int right = n-1;
        int mid;
        while (left<right) {
            mid = left+((right-left)>>1);
            if (a[mid]<k) {
                left = mid+1;
            } else {
                right = mid;
            }
        }
        if (a[left]!=k) {
            printf("-1 -1\n");
            continue;
        }
        printf("%d ", left);

        //left到n找右边界
        right=n;
        while (left+1<right) {
            mid = left+((right-left)>>1);
            if (a[mid]<=k) {
                left = mid;
            } else {
                right = mid;
            }
        }
        printf("%d\n", left);
    }

    return 0;
}