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; } };
难点在查找有序数组中的第一个;找到元素不停止,继续二分查找,直到没有数据可以查询