#include <bits/stdc++.h>
using namespace std;
int n, m;
// 前提：q是一个有序递增的数组,当容器中的元素按照递增的顺序存储时
int q[8] = {1, 2, 3, 3, 3, 4, 5, 7};

//手写二分模板
int lower_bound(int l, int r, int x) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if (q[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

int upper_bound(int l, int r, int x) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if (q[mid] > x)
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

int main() {
    /*
    lower_bound函数返回容器中第一个大于等于目标值的位置
    upper_bound函数返回容器中第一个大于目标值的位置
    若容器中的元素都比目标值小则返回最后一个元素的下一个位置
    */

    int x = 4;
    printf("%lld\n", lower_bound(q, q + 8, x) - q); //大于等于x的第一个位置
    printf("%lld\n", upper_bound(q, q + 8, x) - q); //大于x的第一个位置

    printf("%d\n", lower_bound(0, 8, x)); //大于等于x的第一个位置
    printf("%d\n", upper_bound(0, 8, x)); //大于x的第一个位置

    return 0;
}