题解 | #数字在升序数组中出现的次数#

37、数字在升序数组中出现的次数

解题思路：

题目说的在升序数组找到一个目标，然后统计这个目标出现的次数，我们要好好利用升序数组这个条件。

有了这个条件，我们就可以算出这个目标值的左边界还有右边界，然后取两者之差即可统计出这个目标出现的次数。

因为我们要找到目标值的左边界和右边界，我们很容易能想到用二分查找去求。

那么，找出左边界其实很好找，那要怎么找到右边界呢，我们可以将右边界转化为求比目标值大的数的左边界来求。

也就是说，我们如果要 求数字 4的右边界，那我们其实可以求数字5的左边界然后也就知道了4的右边界了。

代码步骤：

先定位到左边界

接着定位右边界

判断左边界是否符合规范，若超出数组范围，则证明目标值出现的次数为0

否则，右边界减去左边界即能统计出目标出现的次数

动态图演示：

找3的左边界

找3的右边界

代码：

public int GetNumberOfK(int [] array , int k) {
        // 找到左边界
       int first = binarySearch(array,k);
        // 找到右边界（注意：k+1）
       int last = binarySearch(array,k+1);
        // 若超出数组范围，则证明目标值出现的次数为0，否则，右边界减去左边界即能统计出目标出现的次数
        return (first==array.length || array[first]!=k)?0:last-first;
    }

    public int binarySearch(int [] array, int k){
        // 左右边界
        int l = 0, r = array.length;
        while(l < r){
            // 二分求中点
            int m = l+(r-l)/2;
            if(array[m] >= k)
                r = m;
            else
                l = m+1;
        }
        // 返回左边界
        return l;
    }

复杂度分析：

时间复杂度：O(logN)

空间复杂度：O(1)