二分查找

💡

题目链接： 二分查找[牛客]：LC上找不到一模一样的。

题目内容：

描述

请实现有重复数字的升序数组的二分查找。

输出在数组中第一个大于等于查找值的位置（下标从1开始算起），如果数组中不存在这样的数(指不存在大于等于查找值的数)，则输出数组长度加一。

示例1

输入：5,4,[1,2,4,4,5]

返回值：3

说明：输出位置从1开始计算

示例2

输入：5,4,[1,2,3,3,5]

返回值：5

说明：虽然数组中没有4，但 5 ≥ 4 ，所以返回5对应的位置，刚好也是5。

题解(核心代码模式，语言C++)


#include <vector>
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) {
		    // 注意题目中，还有一种找不到的情况，因此 r 初始化为 n，可以设想为在数组最右边插入了一个代表不存在的元素
        int l = 0, r = n;
        // 二分查找模版
        while (l < r) {
		        // 注意，这里二分不建议使用 l+r >> 1, 存在溢出可能
            int mid = l + (r - l) / 2;
            // 核心逻辑，判断目标值和中值的大小, 题目要求是大于等于目标值
            if (v <= a[mid]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        // 注意，下标由 1 开始，因此返回值加 1
        return l + 1;
    }
};