数字在排序数组中出现的次数（剑指offer 面试题38）

原理：
注意数组有排序，如果用二分法找到后，需要向前或向后找，这样的复杂度是O(n)。
更好的思路是用二分查找分别找到第一个和最后一个，最后进行相减得到个数。找第一个的时候，先用二分查找找到数字K，再检测下前一个是否是K，如果是则继续在前面的数组中二分查找，如果不是则当前就是第一个。查找最后一个也是一样的。

算法代码：

    public static int getNumOfK(int[] nums, int K){
        return getLastK(nums,K) - getFirstK(nums,K) + 1;
    }

    private static int getFirstK(int[] nums, int K){
        return getFirstK(nums, K, 0, nums.length);
    }

    private static int getFirstK(int[] nums, int K, int start, int end){
        if(start >= end)
            throw new RuntimeException();

        int mid = (start + end) / 2;
        if(nums[mid]==K){
            if((mid-1)>=start && nums[mid-1]==K){
                return getFirstK(nums, K, start, mid);
            }else{
                return mid;
            }
        }else if(nums[mid]<K){
            return getFirstK(nums, K, mid+1, end);
        }else{
            return getFirstK(nums, K, start, mid);
        }
    }

    private static int getLastK(int[] nums, int K){
        return getLastK(nums, K, 0, nums.length);
    }

    private static int getLastK(int[] nums, int K, int start, int end){
        if(start >= end)
            throw new RuntimeException();

        int mid = (start + end) / 2;
        if(nums[mid]==K){
            if((mid+1)<end && nums[mid+1]==K){
                return getLastK(nums, K, mid+1, end);
            }else{
                return mid;
            }
        }else if(nums[mid]<K){
            return getLastK(nums, K, mid+1, end);
        }else{
            return getLastK(nums, K, start, mid);
        }
    }

测试代码：

        int[] nums = new int[]{1, 2, 3, 3, 4, 4, 4};
        System.out.println(getFirstK(nums, 1));
        System.out.println(getFirstK(nums, 2));
        System.out.println(getFirstK(nums, 3));
        System.out.println(getFirstK(nums, 4));

        System.out.println(getLastK(nums, 1));
        System.out.println(getLastK(nums, 2));
        System.out.println(getLastK(nums, 3));
        System.out.println(getLastK(nums, 4));

        System.out.println(getNumOfK(nums, 1));
        System.out.println(getNumOfK(nums, 2));
        System.out.println(getNumOfK(nums, 3));
        System.out.println(getNumOfK(nums, 4));