题解 | #寻找峰值#

const int maxn=1e5+100;
int a[maxn];
int main()
{
    int n,i,j,q,d;
    cin>>n>>q;  for(i=0;i<n;i++) cin>>a[i];
    while(q--){
        cin>>d;
        int l=0,r=n-1;
        while(l<r){             //找到最先出现的位置，很容易
            int mid=l+r>>1;
            if(a[mid]<d) l=mid+1;
            else r=mid;
        }
        if(a[l]!=d){
            cout<<-1<<" "<<-1<<endl;        //如果找到的最小的下标不是d那么输出-1 -1
            continue;
        }
        int ans1=l;          //第二个二分才是难点
        l=r; r=n;           //r=n了，因为比如待查找元素在[0,n - 1]范围内，可以写成[0,n)，令r = n.
                           //这时候只有两个元素时，r是取最右边元素的后一个位置的，l和r相差2，还会执行循环。
        while(l+1<r){
            int mid=l+r>>1;
            if(a[mid]>d) r=mid; //为什么不令r = mid - 1呢？因为如果按照上一个二分的写法，循环判断条件还是l<r,
            else l=mid;          //当只有两个元素比如2 2时，l指向第一个元素，r指向第二个元素，mid指向第一个元素，
                                //a[mid] <= x，l = mid还是指向第一个元素，指针不移动了，陷入死循环了，此刻l + 1 == r，未能退出循环。
        }
        cout<<ans1<<" "<<l<<endl;
    }
}