题目描述

模板题：整数二分

注意：

1、先找左侧，再找右侧（俩模板记牢即可）；
2、当l = mid（即找右侧）时，mid = l + r + 1 >> 1，否则俩数时候死循环

C++代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
int main(){
    int n,q;
    int a[N];
    cin >> n >> q;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    int k, l, r;
    while(q--){
        cin >> k;
        l = 0, r = n - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(a[mid] >= k)
                r = mid;
            else
                l = mid + 1;
        }
        if(a[l] == k){
            cout << l << " ";
            //这里不要 l = 0，直接在左侧找完的基础上进行查找右侧，岂不是效率更好！！
            r = n - 1;
            while(l < r){
                int mid = l + r + 1 >> 1;
                if(a[mid] <= k)
                    l = mid;
                else
                    r = mid - 1;
            }
            cout << l << endl;
        }else{
            cout << "-1 -1" << endl;
        }
    }

}