2020--09--24 lower_bound

题目描述
请实现有重复数字的有序数组的二分查找。
输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。
示例1
输入
5,4,[1,2,4,4,5]
输出
3
题目思路
看到的一个大神的思路，太强了！！
图片说明
举例分析
现在有一个100个数的数组，要查找的是56的lower_bound

原始数组数据

三个数lo，right，mid以及a[mid]的变化情况

参考代码

public int upper_bound_ (int n, int v, int[] a) {
        // write code here
        if (v > a[n - 1]) return n + 1;//最后一个数比v小
        int lo = 0, right = n;//设置初始值
        while (lo < right) {
            int mid = lo + (right - lo) / 2;
            if (a[mid] < v) {
                lo = mid + 1;
            } else right = mid;
        }
        return lo + 1;
    }

解法二是正常的二分查找
这个的测试通过率是80%，算法复杂度太高

     //write code here
public int upper_bound_ (int n, int v, int[] a) {
        if(a[0]>=v)return 1;
        int left = 0;
        int right = n-1;
        int mid = (left + right)/2;
        while(left<right){
            if(a[mid] >= v){//如果a[mid]>=v,继续判断
                if(a[mid-1]<v){//前一位mid-1<v,满足题意
                    return mid + 1;
                }else{//否则就把mid给right，砍掉右边一半
                    right = mid ;
                }
            }else{//a[mid]<v,把mid给left，砍掉右边一半
                left = mid ;
            }
            mid = (left + right)/2;
        }
        return n+1;