题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

/**
 * 思路：

 * 题目：数的范围
 * 在数组中查找某重复元素的起始位置 和 终点位置，找不到就输出-1 -1，
 *找到了就输出不小于该元素的最小位置和不大于该元素的最大位置。
 * 
 * */

#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int n,m;
int q[N];


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

    int x;
    while(m--)
    {
        cin >> x;
        int l = 0 , r = n - 1;
        // 找到了就输出不小于该元素的最小位置，  q[i] >= x  r = mid ;  else l = mid + 1;
        // l左边的都是小于x的， 结束时存在找到后, l一定是找到的最小位置
        //当查找结束时,l与r相遇，l所在元素若是x则一定是x出现最小位置，因为l左边的元素必然都小于x。

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

        l = 0, r = n - 1;
        while(l < r )
        {
            int mid = l + r +1 >> 1;
            // find 不大于该元素的最大位置。
            if(q[mid] <= x) l = mid;  //q <= x
            else r = mid - 1;    // q > x

        }
        printf("%d\n", q[l]);


    }


    return 0;
}