我曾以为掌握了二分模板就掌握了二分，发现并不是

题目描述

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

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

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

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

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

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

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例:

3 4
5 5
-1 -1

算法1

(二分) $O(logn)$

• 当然二分模板也很重要，模板是背过就好了，这里聊聊这题写check函数，因为老是写不对；
• 题意是询问x元素在序列的左右下标，不妨直接聊对于左端点的check函数怎么写的；
• 考虑左端点的位置：
  • 找出大于等于x的最小值呢？（A思路）
  • 找出小于x的最大值呢？(B思路)
• 最后发现，上面两种思路个都可以写，但是区别是其中有一个写得比较别扭，即考虑A思路比B思路要好，为什么？
  • 比方说，上面样例 1 2 2 3 3 4 找出3的左端点；
  • （A思路） 二分之后得到的r是落在[3]这个位置，明显这就是题目要输出的答案
  • （B思路） 二分之后得到的r是落在[2]这个位置
• 所以，check函数要想好的话，就要从题目出发，下面给出这两种思路的代码对比。

C++ 代码 1 （A 思路）

• 对于左端点：找出大于等于x的最小值
• 对于右端点：找出小于等于x的最大值

#include <iostream>

using namespace std;
const int N = 1e5 + 10;
int q[N];

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

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

    while (T --)
    {
        int x;
        scanf("%d", &x);

        int l = 0, r = n - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }

        if (q[r] != x) puts("-1 -1");
        else {
            printf("%d ", r);

            l = 0, r = n - 1;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }
            printf("%d\n", r);
        }
    }

    return 0;
}

C++ 代码 2 （B 思路）

• 对于左端点：找出小于x的最大值
• 对于右端点：找出大于x的最小值

#include <iostream>

using namespace std;
const int N = 1e5 + 10;
int q[N];

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

    while(T --)
    {
        int x;
        scanf("%d", &x);

        int l = 0, r = n - 1;
        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < x) l = mid;
            else r = mid - 1;
        }

        if (q[r + 1] != x) puts("-1 -1");
        else {
            printf("%d ", q[r] == x ? r : r + 1); // 可能左端点找不出小于`x`的最大值，若找到答案是r + 1， 找不到的话，答案是r

            l = 0, r = n - 1;
            while(l < r)
            {
                int mid = l + r >> 1;
                if (q[mid] > x) r = mid;
                else l = mid + 1;
            }

            printf("%d\n", q[r] == x? r : r - 1); // 可能右端点找不出大于`x`的最小值，若找到答案是r - 1， 找不到的话，答案是r
        }
    }
    return 0;
}