题目描述

找x，
如果存在，输出所求元素的起始位置和终止位置
如果不存在，输出-1 -1

算法1

(y总强大的模板) $O(logN)$

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int q[N];

int main()
{
    int n, m;
    cin >> n >> m;

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

    while (m--)
    {
        int x;
        cin >> x;

        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid; //对于3...3 要找到的mid都要大于等于3，然后往左找左边界
            else l = mid +1;
        }
        if (q[l] != x) 
        {
            cout << "-1 -1" << endl;
            continue;
        }
        cout << l << ' ';

        l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] <= x) l = mid;  ////对于3...3 找到的mid都要小于等于3, 往右找右边界
            else r = mid - 1;
        }
        cout << l << endl;
    }

    return 0;
}

算法2

(STL函数) $O(logN)$ ??

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int q[N];

int main()
{
    int n, m;
    cin >> n >> m;

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

    while (m--)
    {
        int x;
        cin >> x;
        if (!binary_search(q, q + n, x))
            cout << "-1 -1" << endl;
        else 
            cout << lower_bound(q, q + n, x) - q<< ' ' << upper_bound(q, q + n, x) - q - 1 << endl;
    }

    return 0;
}