0.问题描述

题目描述
请实现有重复数字的有序数组的二分查找。
输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。

输入 5,4,[1,2,4,4,5]
返回值 3
说明 输出位置从1开始计算

看完题目就确定是二分查找，不用过脑

    /**
     * 二分查找
     * @param n int整型 数组长度
     * @param v int整型 查找值
     * @param a int整型一维数组 有序数组
     * @return int整型
     */
  public int upper_bound_(int n, int v, int[] a) {
        int left = 0;
        int rigth = n - 1;
        int center = (rigth + left) / 2;
        while (rigth >= left) {
            center = (rigth + left) / 2;
            if (a[center] == v) {
                return center + 1;
            } else if (a[center] > v) {
                rigth = center - 1;
            } else if (a[center] < v) {
                left = center + 1;
            }
        }
        return n + 1;
    }

提交代码后，提示运行超时

1.问题分析

看到提交结果后，有点懵，再次审题，才发现，题目要求的是查找第一个大于等于查找值的位置

给的示例太具有迷惑性了，在[1,2,4,4,5]中，查找4，返回值是3
但是，如果是在[1,4,4,4,5]中，查找4，返回值应该是2
在[4,4,4,4,5]中，查找4，返回值应该是1

问题点在于：在有重复数字的有序数组中查找第一个大于等于查找值的位置。

满足要求的中间值要同时符合什么条件？

 1.中间值`大于等于`目标值
 2.中间值的`前一个值`要小于目标值

以[1,4,4,4,5]为例分析

第一次查找:查找区域为[1,4,4,4,5]
左指针指向第一个元素1，右指针指向最后一个（第5个）元素5
中间指针指向第三个元素4，正好等于目标值 `符合条件1`
但是此时中间值的前一个值（第二个元素）为4，刚好等于目标值，`不符合条件2`

二分区域`缩圈`为[1,4]
左指针指向第一个元素1，右指针指向最后一个（第2个）元素4
中间指针指向第二个元素4，正好等于目标值，`符合条件1`
中间值的前一个值（第一个元素）为1，`符合条件2` 【此处需要注意的是，中间值的前一个值可能不存在的情况】
满足条件，返回2

2.问题深化及解决

在二分查找的基础上进行修改即可

    /**
     * 二分查找
     * @param n int整型 数组长度
     * @param v int整型 查找值
     * @param a int整型一维数组 有序数组
     * @return int整型
     */
     public int upper_bound_(int n, int v, int[] a) {
        if (v > a[n - 1]) {
            return n + 1;
        }
        int left = 0;
        int rigth = n - 1;
        while (rigth >= left) {
            int center = (rigth + left) / 2;
            int centerValue = a[center];
            if (center - 1 < 0) {//此处需注意
                return center + 1;
            } else {
                if (centerValue >= v && a[center - 1] < v) {//此处需注意
                    return center + 1;
                } else if (centerValue >= v) {//此处需注意
                    rigth = center - 1;
                } else if (centerValue < v) {
                    left = center + 1;
                }
            }
        }
        return n + 1;
    }