二分法的应用（求有序序列第一个满足某个条件的元素的位置的方法）

二分法求 有序序列第一个满足某个条件的元素的位置的方法（模版）：

//二分区间为左闭右闭[left, right],初始值left、right必须覆盖解的所有可能
int solve(int left, int right){
    int mid;
    while(left < right){ //对于[left,right]来说， left == right意味着找到了解 
         mid = (left + right) / 2;
         if(条件成立){ //条件成立，第一个满足条件的元素的位置 <= mid
              right = mid; //往左子区间[left, mid]查找
         } else {
              left = mid + 1; //往右子区间[mid + 1, right]查找 
         }
    }
}

应用一：求第一个大于某个值x的元素的位置

int upper_bound(int A[], int left, int right, int x){
    int mid;
    while(left < right){
        mid = (left + right) / 2;
        if(A[mid] > x){
            right = mid;
        }else{
            left = mid + 1;
        }
    }
    return left;
}

应用二：求第一个大于等于某个值x的元素的位置

将判断条件 > 改为 >= 即可

数有序列中有多个相同的元素 ：寻找第一个大于等于x的元素的位置L和第一个大于x的元素的位置R , 则 [L,R) 内的元素都等于x