题目描述

拐进链接

方法1

(二分) $O(logn)$

直接看代码注释啦~~

模板一：

while(l < r)        //寻找右边界
{
    int mid = (l + r + 1) >> 1;     
    if(q[mid] <= x) l = mid;    //当l = mid时,上面mid = (l + r + 1) >> 1,否则会出现死循环
    else r = mid - 1;       //q[mid] > x 取不到mid,只能取到mid - 1 只因为他是整数二分~
}

模板二：

while(l < r)        //寻找左边界
{
    int mid = l + r >> 1;
    if(q[mid] >= x) r = mid;
    else l = mid + 1;
}

对于模板一，可以在O(logn)的时间内查询到，但是试想一下，如果给定的数字列中有几个相同的元素，而且最后的要求就是找出这个数字的位置，那么会找到第几个呢？没错，只能找到第一个和最后一个，就跟upperbound极其类似。模板一寻找的是左边界的值，思考一下就会发现，条件是小于等于x，那么只要是小于等于x的都是吗，满足这个条件的，mid是在l的右边的，让l等于mid就相当于右移左边界，直到最右边一个元素，此时左边都是满足小于等于x的数字，模板二则恰恰相反，模板二能找到左边界，因为从左边界往后，都是满足大于等于x的数字

参考文献

yxc

C++ 代码

#include <iostream>

using namespace std;

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

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i ++) cin >> 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;        //从左边界往右都是大于等于x的，所以找到的是左边界
            else l = mid + 1;
        }
        if(q[l] != x) cout << -1 << ' ' << -1 << endl;
        else 
        {
            cout << l << ' ';
            l = 0, r = n - 1;
            while(l < r)
            {
                int mid = (l + r + 1) >> 1;
                if(q[mid] <= x) l = mid;    //从右边界往左找到的都是小于等于x的，找的的是右边界
                else r = mid - 1;
            }
            cout << l << endl;
        }
    }

    return 0;
}

方法2

(stl)

注意，lower_bound返回的是查找位置的指针(地址)，所以需要下标的话，需要减去数组的首地址，lower_bound返回的是大于等于当前元素的地址，upper_bound返回的是大于这个元素的地址,也就是说，在相同的元素之间，lower_bound返回的是第一个元素，upper_bound返回的是最后一个元素后一个元素的下标，需要最后一个下标的时候需要减去1

C++ 代码

#include <iostream>
#include <algorithm>        //upper_bound必须包含这个头文件
using namespace std;

const int N = 100010;
int q[N];
bool flag[10010];       //hash一下是否出现过

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i ++) 
    {
        cin >> q[i];
        flag[q[i]] = true;
    }

    while(m --)
    {
        int a;
        cin >> a;
        if(flag[a] == true)         
            cout << (lower_bound(q, q + n, a) - q) << " " << (upper_bound(q, q + n, a) - q) - 1 << endl;
        else cout << -1 << ' ' << -1 << endl;
    }

    return 0;
}