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

public class Solution {
    public int GetNumberOfK(int [] array, int k) {
        // 数组为空或者数组元素个数为0，直接返回
        if (array == null || array.length == 0) {
            return 0;
        }
        // 使⽤⼆分法，找出等于k的数的索引
        int index = findIndex(array, k, 0, array.length - 1);
        // 索引为-1，则说明该数不存在
        if (index == -1) {
            return 0;
        }
        // 存在则index处存在⼀个
        int count = 1;
        // 向左边拓展，计算相等的个数
        for (int left = index - 1; left >= 0; left--) {
            if (array[left] == k) {
                count++;
            }
        }
        // 向右边拓展，计算相等的个数
        for (int right = index + 1; right < array.length; right++) {
            if (array[right] == k) {
                count++;
            }
        }
        return count;
    }

    /**
     * 二分查找出k值的索引
     * */
    public int findIndex(int[] array, int k, int left, int right) {
        // 只剩下⼀个数，直接和k⽐较
        if (left == right) {
            return array[left] == k ? left : -1;
        } else {
            // 中间的数索引为mid。将数组分为两半
            int mid = left + (right - left) / 2;
            // 等于k直接返回当前索引
            if (array[mid] == k) {
                return mid;
            } else if (array[mid] < k) {
                // mid索引的数⼩于k，则k只可能在右边⼀半
                return findIndex(array, k, mid + 1, right);
            } else {
                // 否则在左边⼀半
                return findIndex(array, k, left, mid - 1);
            }
        }
    }
}

解题思想：二分查找k值索引，左右移动统计次数。