二分法找数的范围

二分的过程就不说了，在这里主要记录一下如何找到左右边界
左边界： q[mid] >= k; //意思是找到最靠左的 >= k的数的位置，边界的更新：yes : r = mid; no : l = mid + 1;
有边界： q[mid] <= k; //意思是找到最靠右的 <= K的数的位置，边界的更新: yes : l = mid; no : r = mid - 1;

k <= q[mid] <= k,这样写的话就很容易理解了

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n,m;
int q[N];
int main(){
    cin >> n >> m;
    for(int i = 0;i < n;++i)
        cin >> q[i];
    while(m--){
        int k;
        cin >> k;
        int l = 0,r = n - 1;
        while(l < r){
            int mid = (l + r) / 2;
            if(q[mid] >= k) r = mid;
            else l = mid + 1;
        }
        if(q[l] != k) cout <<"-1 -1" <<endl;
        else{
            cout << l <<" ";
            int l = 0,r = n - 1;
            while(l < r){
                int mid = (l + r + 1) / 2;
                if(q[mid] <= k) l = mid;
                else r = mid - 1;
            }
            cout << l << endl;
        }
    }
    return 0;
}