牛客题霸 二分查找 C++题解/答案

题目描述

请实现有重复数字的有序数组的二分查找。
输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。
示例1
输入
复制
5,4,[1,2,4,4,5]
返回值
复制
3

题解：

二分模板题
如果是学竞赛的应该很懂
二分的本质就像是翻字典，一开始l=0，r=n，先翻到最中间（mid=(r+l)/2），然后看目标单词是在左侧还是右测，如果是在左侧，我们就继续翻左侧的中间页，重复上述操作，l=0,r=mid-1，mid=(l+r)>>1

代码：

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
        int l=0;
        int r=n-1;
        if(a[n-1]<v)return n+1;
        while(l<=r)
        {
   
            int mid=(l+r)>>1;
            //if(a[mid]==v)return mid+1;
            if(a[mid]<v)l=mid+1;
            else r=mid-1;
        }
        return l+1;
    }
};