单调 => 二分
整数二分注意事项
1、关于是否 +1
如果 mid 属于左半集合则不 +1 ,此时 mid = l + r / 2 向下取整
如果 mid 属于右半集合则需 +1 ,此时 mid = l + r / 2 向上取整
注:( l + r + 1 ) / 2 = ( l + r + 2 - 1 ) / 2 = ( l + r ) / 2 向上取整
2、l ≡ r + 1
l = mid; r = mid - 1;
r = mid; l = mid + 1;
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N];
int main()
{
int n, m;
cin >> n >> m;
for(int i = 0; i < n; ++ i)
scanf("%d",&q[i]);
while(m --)
{
int x;
cin >> x;
int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r >> 1;
if(q[mid] >= x) r = mid;
else l = mid + 1;
}
if(q[l] == x) cout << l << " ";
else cout << "-1 ";
l = 0, r = n - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(q[mid] <= x) l = mid;
else r = mid - 1;
}
if(q[l] == x) cout << l << endl;
else cout << "-1\n";
}
return 0;
}