[2020.10.14] 二分查找-找第一个出现的数字

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) {
        // write code here
        // 使用迭代器，避免越界
        auto begin = a.begin();
        auto end = a.end();

        // 有序数组可以考虑避免不存在的数字，不使用也行，若存在此种情况，后续begin会指向最后end。仅仅避免后续的
        if ((a.end() - 1) < v) {
            return n + 1;
        }

        // 需要找到第一个出现的值，即使找到了数据也不停止，直到begin == end 结束为止
        while (begin < end) {
            auto mid = begin + (end - begin) / 2; 
            if (*mid < v) {
                // begin 右移
                begin = mid+1;
            } 
            if (*mid >= v) {
                // 已经找到数据，还需要继续完成查找，不断修正
                // end 移动到mid，保持end指向范围下一位
                end = mid;
            }
        }
        // 如果查找到了，此时begin已经指向确定的数据
        // 没有找到的数据在前面已经避免了，
        return begin - a.begin() + 1;
    }
};

难点在查找有序数组中的第一个；找到元素不停止，继续二分查找，直到没有数据可以查询