二分查找（二分）

题意

求一个单调递增数组中,首个出现的大于等于给定值v的位置.下标是1-index

思路分析

C++库函数

有库函数直接可以实现

return (lower_bound(a.begin(),a.end(),v) - a.begin()) + 1 ;

数组上单调性质

对于数组来说,a[0]到a[n-1], 单调递增.

二分法

有了单调性质后,考虑二分.

定义左右值

l左值,它的初始值小于/等于/大于 v, 但修改的最终要大于等于v

r右值,它的值大于等于v

每次取均值(l+r)/2,检验与x大小关系后更新l或r

直到l == r,输出l即可

题目样例

以题目样例5,4,[1,2,4,4,5]为例

题解

所以整合上面的内容

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) {
        int l = 0; // 左值可能小于/等于/大于,但最终要是 大于等于
        int r = n; // 右值一定 大于等于
        while (l < r) {
            int m = (l+r)/2;
            if (a[m] < v) { // 值更大
              l = m + 1;
            }else{
              r = m;
            }
        }
        return l + 1; // 长度大于
    }
};

复杂度分析

空间复杂度: 只用了常数个额外变量,所以空间复杂度为$O(1)O(1)$

时间复杂度: 每次让左右值间距减半,所以时间复杂度为$O(log(n))O(log(n))$