AcWing 789. 数的范围 （二分）

原题链接

思路

见代码注释

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N];int main()
{
    cin >> n >> m;//从0开始存for (int i = 0; i < n; i ++ ) cin >> a[i];while (m -- )// m次询问{
    int l, r, c;cin >> c; //输入要找的数l = 0, r = n - 1; //规定范围int x, y;while (l < r) //标准二分模板 l < r{
    int mid = l + r >> 1; //二分if (a[mid] >= c) //如果找到的数大于等于要找的数，说明要缩小范围{
    r = mid;//因为有等于，所以不能-1，这样可以实现一步步往左走，直到走到左端点}else//如果找到的数小于要找的数，说明要增大范围里的数{
    l = mid + 1;}}//不存在的情况if (a[l] != c) {
    cout << "-1 -1" << endl;continue; //没有进行下去的必要了}cout << l << " ";l = 0, r = n - 1;//和上面同理while (l < r){
    int mid = l + r + 1>> 1;if (a[mid] > c){
    r = mid - 1;//最右边的一步到位的确定后}else{
    l = mid;//l慢慢向r靠经y = l;}}cout << r << endl;}return 0;
}

总结

学好二分很重要