【牛客题霸题解】二分查找

题目要求：在有序数组 中查找第一个大于等于给定值 的位置，如果不存在，输出数组的长度 加一。
先考虑这样一个问题：对于一个有序数组来说，什么情况下是不存第一个大于等于 的位置呢？
即：数组中的所有数都比 小，可以写成

if(a[n-1]<v)
    return n+1;

判完这个条件以后， 数组里就一定可以存在一个位置是答案了。这样的话，我们来设答案在闭区间之间
当这个区间只剩下一个数，即的时候，就是我们答案的位置了。
最开始，可能的区间为整个 数组
下面我们用二分的方式对这个区间进行缩减
每次拿出中间的值 和 比较，那会有三种结果:大于、等于、小于

1、如果
说明说明后面的那段都不可能是结果了。因为a[Mid]就是一个大于等于v的值了，后面的肯定都不可能是第一个。这样的话，可能的答案区间就缩减成了
即

Right = Mid;

2、如果
这种情况和1相同
3、如果
那说明，以及之前的都不可能是我们的结果，可能的答案区间缩减成了。
即

Left = Mid+1;

因为现在数组中肯定有一个位置是我们要求的结果，所以在缩减区间的过程中不会出现的情况。所以，当的时候我们就找到答案了，这个答案就是Left(Right),还要注意一点，本题要输出的位置是从1开始的，但是我们的区间是用的数组下标，所以最后要输出Left+1(Right+1)。
C++代码

class Solution {
public:
    int upper_bound_(int n, int v, vector<int>& a) {
        if(a[n-1]<v){return n+1;}//如果不存在这样的数：即数组中所有数字都比
        int Left = 0;
        int Right = n-1;
        while(Left < Right)
        {
            int Mid = Left+(Right-Left)/2;//防溢出
            if(a[Mid]>=v){Right = Mid;}
            else{Left = Mid+1;}
        }
        return Left+1;
    }
};

java代码

    public int upper_bound_ (int n, int v, int[] a) {
        if(a[n-1]<v){return n+1;}//如果不存在这样的数：即数组中所有数字都比
        int Left = 0;
        int Right = n-1;
        while(Left < Right)
        {
            int Mid = Left+(Right-Left)/2;//防溢出
            if(a[Mid]>=v){Right = Mid;}
            else{Left = Mid+1;}
        }
        return Left+1;
    }

python代码

class Solution:
    def upper_bound_(self , n , v , a ):
        # write code here
        if a[n-1]<v:
            return n+1;#如果不存在这样的数：即数组中所有数字都比
        Left = 0;
        Right = n-1;
        while Left < Right:
            Mid = (Left+Right)//2;
            if a[Mid]>=v:
                Right = Mid;
            else:
                Left = Mid+1;
        return Left+1;