0.問題描述

題目描述
請實現(xiàn)有重復(fù)數(shù)字的有序數(shù)組的二分查找。
輸出在數(shù)組中第一個大于等于查找值的位置，如果數(shù)組中不存在這樣的數(shù)，則輸出數(shù)組長度加一。

輸入 5,4,[1,2,4,4,5]
返回值 3
說明 輸出位置從1開始計算

看完題目就確定是二分查找，不用過腦

    /**
     * 二分查找
     * @param n int整型 數(shù)組長度
     * @param v int整型 查找值
     * @param a int整型一維數(shù)組 有序數(shù)組
     * @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.問題分析

看到提交結(jié)果后，有點懵，再次審題，才發(fā)現(xiàn)，題目要求的是查找第一個大于等于查找值的位置

給的示例太具有迷惑性了，在[1,2,4,4,5]中，查找4，返回值是3
但是，如果是在[1,4,4,4,5]中，查找4，返回值應(yīng)該是2
在[4,4,4,4,5]中，查找4，返回值應(yīng)該是1

問題點在于：在有重復(fù)數(shù)字的有序數(shù)組中查找第一個大于等于查找值的位置。

滿足要求的中間值要同時符合什么條件？

 1.中間值`大于等于`目標(biāo)值
 2.中間值的`前一個值`要小于目標(biāo)值

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

第一次查找:查找區(qū)域為[1,4,4,4,5]
左指針指向第一個元素1，右指針指向最后一個（第5個）元素5
中間指針指向第三個元素4，正好等于目標(biāo)值 `符合條件1`
但是此時中間值的前一個值（第二個元素）為4，剛好等于目標(biāo)值，`不符合條件2`

二分區(qū)域`縮圈`為[1,4]
左指針指向第一個元素1，右指針指向最后一個（第2個）元素4
中間指針指向第二個元素4，正好等于目標(biāo)值，`符合條件1`
中間值的前一個值（第一個元素）為1，`符合條件2` 【此處需要注意的是，中間值的前一個值可能不存在的情況】
滿足條件，返回2

2.問題深化及解決

在二分查找的基礎(chǔ)上進(jìn)行修改即可

    /**
     * 二分查找
     * @param n int整型 數(shù)組長度
     * @param v int整型 查找值
     * @param a int整型一維數(shù)組 有序數(shù)組
     * @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;
    }