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

//二分算法之手动版本
int manual_lower_bound(int l, int r, int x) {
    while (l < r) {
        int mid = (l + r) / 2;
        if (q[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}

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

int main() {
    /**********************************************************/
    //方法1：yxc 大法
    //从0~6找出>=3的第一个位置
    l = 0, r = 6;
    int x = 3;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (q[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    printf("%d\n", l);

    //从0~6找出<=3的最后一个位置
    l = 0, r = 6;
    x = 3;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (q[mid] <= x)
            l = mid;
        else
            r = mid - 1;
    }
    printf("%d\n", l);
    /*
    方法2：STL lower_bound,upper_bound 大法
    lower_bound函数返回容器中第一个大于等于目标值的位置
    upper_bound函数返回容器中第一个大于目标值的位置
    若容器中的元素都比目标值小则返回最后一个元素的下一个位置
    */
    printf("%lld\n", lower_bound(q, q + 7, x) - q);
    printf("%lld\n", upper_bound(q, q + 7, x) - q - 1);
    /**********************************************************/
    /*
    方法3：手写 lower_bound,upper_bound大法
    */
    printf("%d\n", manual_lower_bound(0, 7, x));
    printf("%d\n", manual_upper_bound(0, 7, x) - 1);
    /**********************************************************/
    return 0;
}