Lower_bound 和 upper_bound 完成的整数二分。

2020/4/10更新了简洁一点的写法

#include <bits/stdc++.h>
using namespace std;

inline void solve(int k, vector<int> &v) {
    int l = lower_bound(v.begin(), v.end(), k) - v.begin();
    int r = upper_bound(v.begin(), v.end(), k) - v.begin();
    if(v[l] == k) printf("%d ", l);
    else printf("-1 ");
    if(v[r - 1] == k) printf("%d\n", r - 1);
    else printf("-1\n");
}

int main(){
    int n, q, k, tmp;
    cin >> n >> q;
    vector<int> v;
    for(int i = 0; i < n; i ++) {
        cin >> tmp; v.push_back(tmp);
    }
    while(q --) {
        cin >> k;
        solve(k, v);
    }
    return 0;
}

C++ 代码

#include <bits/stdc++.h>
using namespace std;

#define Rep(i, a, b) for(int i = a; i <= b; i ++)
#define Debug(x)     cout << "[" << #x <<": " << (x) <<"]"<< endl

const int N = 1e5 + 10;
int n, Q;
int a[N];

const int BUFSIZE=20 << 20; //40M
char Buf[BUFSIZE+1], *buf = Buf;
template<class T>
inline void read(T &a){
    int sgn = 1;
    for(a=0;*buf<'0'||*buf>'9'; buf++) if(*buf=='-') sgn = -1;
    while(*buf>='0'&&*buf<='9'){ a=a*10+(*buf-'0'); buf++; }
    a *= sgn;
}

inline void solve(int val)
{
    int l = lower_bound(a, a+n, val) - a;
    int r = upper_bound(a + l, a+n, val) - a;
    if(a[l] == val) printf("%d ", l);
    else printf("-1 ");
    if(a[r - 1] == val) printf("%d\n", r - 1);
    else printf("-1\n");
}

int main()
{
    fread(Buf, 1, BUFSIZE, stdin);
    read(n), read(Q);
    Rep(i, 0, n - 1) read(a[i]);

    while(Q --)
    {
        int val; read(val);
        solve(val);
    }
    return 0;
}