博客

二分查找

OJ 地址：

二分查找

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