956-二分查找数字的插入位置

956-二分查找数字的插入位置 题目如下

请实现有重复数字的有序数组的二分查找。
输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。
输入：5,4,[1,2,4,4,5]
输出：3
参数解释：
* @param n int整型 数组长度
* @param v int整型 查找值
* @param a int整型vector 有序数组
* @return int整型

解题代码

查找第一个大于等于他的为止，那么相等的时候，就继续向左寻找，最后返回left，简单的二分查找思想，和STL里面的lower_bound基本相似思想。

int lower_bound (int n, int v, vector &a)
{
    // write code here
    if (n <= 0 || a[0] > v || a[n - 1] < v)
    {
        return n + 1;
    }
    int left = 0;
    int right = v - 1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (a[mid] > v)
        {
            right = mid - 1;
        }
        else if (a[mid] < v)
        {
            left = mid + 1;
        }
        else
        {
            //相等的话
            right = mid - 1; //左边继续找
        }
    }
    return (left < 0 || left >= n) ? n + 1 : left + 1;
}