算法基础班–第一章–3.整数二分模板

算法模板

模板1：下取整

int bsearch_1(int l, int r) {
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid))  r = mid;
        else l = mid + 1；
    }
    return l;
}

模板2：上取整

int bsearch_2(int l, int r) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid))  l = mid;
        else r = mid - 1；
    }
    return l;
}

本题完整代码

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 100010;
int n, m;
int q[N];


int main() {
    scanf("%d%d", &n, &m); // n, m 数组的长度和询问的个数
    for (int i = 0; i < n; i++) scanf("%d", &q[i]);
    while (m--){  // 共有m 个询问
        int x;
        cin >> x;
        int l = 0, r = n - 1; // 先二分起始坐标（题目说了从0开始计数）
        while (l < r) {
            int mid = l + r >> 1;  //不用管，直接先写上 mid = l + r >> 1; 后面根据实际情况看是否+1
            if (q[mid] >= x) r = mid;  // 这里找的是x的起始坐标！！！
            else l = mid + 1;
        }

        if (q[l] != x) cout << "-1 -1" << endl; // 此处 l == r
        else {
            cout << l << ' '; // 此处 l == r
            int l = 0, r = n - 1;  // 重新将i, j 赋为初始值!!
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) l = mid; //这里找的是x的终止坐标！！！
                else r = mid - 1;
            }
            cout << l << endl; // 此处 l == r
        }
    }
    return 0;
}