整数二分(besearch)

题目描述

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

(二分) O(nlogn)

枚举左端点和右端点

C++ 代码

#include <bits/stdc++.h>

using namespace std;

#define N 1000010

int n, k, q, a[N];

// 查找元素q在数组a中的首次和最后一次出现的位置
void bearch(int q) {
    // leftans和rightans用于存储结果，初始化为最大值和最小值
    int leftans = INT_MAX, rightans = INT_MIN;
    int l = 0, r = n - 1;

    // 找到元素q的首次出现位置
    while (l < r) {
        int mid = (l + r) >> 1;  // 等价于 (l + r) / 2
        if (a[mid] >= q)
            r = mid;
        else 
            l = mid + 1;
    }

    // 如果在数组a中没有找到元素q，输出-1 -1
    if (a[l] != q) {
        printf("-1 -1\n");
        return;
    }

    // 输出元素q的首次出现位置
    printf("%d ", l);

    // 重置左右边界，准备查找最后一次出现位置
    l = 0, r = n - 1;

    // 找到元素q的最后一次出现位置
    while (l < r) {
        int mid = (l + r + 1) >> 1;  // 等价于 (l + r + 1) / 2
        if (a[mid] <= q)
            l = mid;
        else 
            r = mid - 1;
    }

    // 输出元素q的最后一次出现位置
    printf("%d\n", l);
    return;
}

int main() {
    // 输入数组长度n和查询次数k
    scanf("%d %d", &n, &k);

    // 输入数组元素
    for (int i = 0; i < n; ++i)
        scanf("%d", a + i);

    // 对每个查询执行bearch函数
    while (k--) {
        scanf("%d", &q);
        bearch(q);
    }

    return 0;
}

算法2

(upperbound 和 lowerbound) O(nlogn)

STL

大法好！！！

#include <bits/stdc++.h>

using namespace std;

#define N 1000010

int n, k, q, a[N];

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; ++i)
        scanf("%d",a + i);
    while (k--) {
        scanf("%d", &q);
        int t = lower_bound(a, a + n, q) - a;

        if (t == n || a[t] != q) {
            puts("-1 -1");
            continue;
        }

        printf("%d ", t);

        t = upper_bound(a, a + n, q) - a;
        printf("%d\n", t - 1);
    }
    return 0;
}