剑指 offer 笔记 37 | 数字在排序数组中出现的次数

题目描述
统计一个数字在排序数组中出现的次数。

思路分析
这道题目指出排序的关键字，我们可以联想到这是一组有顺序的数组，可以暴力直接循环，但不推荐，面试官也不喜欢。

那么可以用二分查找，对数组中间的数字与 K 比较。
1）如果中间数字 > K,那么 K 只有可能出现在数组前半段，下一次我们只需在前半段查找即可。
2）如果中间数字 < K，那么 K 只有可能出现在数组后半段，下一轮只需在后半段查找。
3）如果中间数字 == K，那么得判断这数字是不是第一个 K ，如果不是，那么这个数字就是第一个 K；如果中间数字前面也是一个 K，那么第一个 K 在前半段，下一次我们需要在数组前半段查找。

4)同理，也可以得到最后一个 K。

解释说明：

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int length = array.length;
        if(length == 0){
            return 0;
        }
        int firstK = getFirstK(array, k, 0, length-1);
        int lastK = getLastK(array, k, 0, length-1);
        if(firstK != -1 && lastK != -1){
             return lastK - firstK + 1;
        }
        return 0;
    }
    //递归写法
    private int getFirstK(int [] array , int k, int start, int end){
        if(start > end){
            return -1;
        }
        int mid = (start + end) >> 1;
        if(array[mid] > k){
            return getFirstK(array, k, start, mid-1);
        }else if (array[mid] < k){
            return getFirstK(array, k, mid+1, end);
        }else if(mid-1 >=0 && array[mid-1] == k){
            return getFirstK(array, k, start, mid-1);
        }else{
            return mid;
        }
    }
    //循环写法
    private int getLastK(int [] array , int k, int start, int end){
        int length = array.length;
        int mid = (start + end) >> 1;
        while(start <= end){
            if(array[mid] > k){
                end = mid-1;
            }else if(array[mid] < k){
                start = mid+1;
            }else if(mid+1 < length && array[mid+1] == k){
                start = mid+1;
            }else{
                return mid;
            }
            mid = (start + end) >> 1;
        }
        return -1;
    }
}

链接：https://www.nowcoder.com/questionTerminal/70610bf967994b22bb1c26f9ae901fa2?f=discussion
来源：牛客网