注意

不会输出0，该题的“位置”是从1开始计数的

核心思路

始终维护答案在左闭右闭的 [l, r] 区间内

编码思路：

1. 为了方便访问 vector ,先不考虑从 1 开始计数的的问题，假设答案的范围是 [0, n]（实际输出的就是 [1, n+1] )
2. 保持 [l, r] 是答案所在的区间，终止条件即 l == r
3. 每次检验 a[mid] 与查找值 v 的关系来进一步确定答案所在的区间
4. 如果 a[mid] < v ，答案一定在 [mid+1, r] 区间，否则答案一定在 [l, mid] 区间

class Solution {
public:
    /**
     * 二分查找
     * @param n int整型 数组长度
     * @param v int整型 查找值
     * @param a int整型vector 有序数组
     * @return int整型
     */
    int upper_bound_(int n, int v, vector<int>& a) {
        int l = 0, r = n;
        while(l < r){    //    2. 保持 [l, r] 是答案所在的区间，终止条件即 l == r
            int mid = (l + r) / 2;    //    3. 每次检验 a[mid] 与查找值 v 的关系来进一步确定答案所在的区间
            if(a[mid] < v){    //    4.  如果 a[mid] < v ，答案一定在 [mid+1, r] 区间，否则答案一定在 [l, mid] 区间
                l = mid + 1;
            }
            else{
                r = mid;
            }
        }
        return l + 1;    // 1. 为了方便访问vector,先不考虑从1开始计数的的问题，假设答案的范围是 [0, n]（实际输出的是 [1, n+1] )
    }
};