数字在排序数组中出现的次数

【题目】

题目来源于头条面试的一道算法题，如下：

给一个排序好的数组，里面有重复元素。
例子：[5, 5, 5, 7, 12, 12, 12, 13, 15]，
找出给定的一个数的最小和最大index,比如12，返回[4, 6],
如果没有返回[-1, -1]，考虑下时间复杂度。

其实这道题跟剑指offer上一道面试题很类似，原题如下：

统计一个数字在排序数组中出现的次数。例如输入排序数组{1,2,3,3,3,3,4,5}和数字3，
由于3在这个数组中出现了4次，因此输出4。

【思路】

既然输入的数组是排序的，那么我们很自然地就能想到用二分查找算法。但是又不能直接使用二分查找，必须要对二分查找进行改进，可以看到两道题的关键都在于如何找到第一个k和最后一个k的位置。
我们先分析如何用二分查找算法在数组中找到第一个k。我们看中间的数字和k相等这种情况，我们先判断这个数字是不是第一个k。如果位于中间数字的前面一个数字不是k，此时中间的数字刚好就是第一个k。如果中间数字的前面一个数字也是k，也就是说第一个k肯定在数组的前半段，下一轮我们仍然需要在数组的前半段查找。
我们可以用同样的思路在排序数组中找到最后一个k。我们看中间的数字和k相等这种情况，我们先判断这个数字是不是最后一个k。如果位于中间数字的后面一个数字不是k，此时中间的数字就是最后一个k。如果中间数字的后面一个数字也是k，也就是说最后一个k肯定在数组的后半段，下一轮我们仍然需要在数组的后半段查找。

【实现代码】

public class GetNumberOfK {
    public int getFirstK(int[] arr, int k, int low, int high){
        if (low > high){
            return -1;
        }
        int mid = (low + high) / 2;
        if (k == arr[mid]){
            if ((mid > 0 && arr[mid - 1] != k) || mid == 0){
                return mid;
            } else {
                high = mid - 1;
            }
        } else if(k < arr[mid]){
            high = mid - 1;
        } else {
            low = mid + 1;
        }
        return getFirstK(arr, k, low, high);
    }

    public int getLastK(int[] arr, int k, int low, int high){
        if (low > high){
            return -1;
        }
        int mid = (low + high) / 2;
        if (k == arr[mid]){
            if ((mid < arr.length - 1 && arr[mid + 1] != k) || mid == arr.length - 1){
                return mid;
            } else {
                low = mid + 1;
            }
        } else if (k < arr[mid]){
            high = mid - 1;
        } else {
            low = mid + 1;
        }
        return getLastK(arr, k, low, high);
    }

    public int getNumberOfK(int[] arr, int k){
        int result = 0;

        if (arr != null && arr.length > 0){
            int first = getFirstK(arr, k, 0, arr.length - 1);
            int last = getLastK(arr, k, 0, arr.length - 1);
            if (first > -1 && last > -1){
                result = last - first + 1;
            }
        }
        return result;
    }
}

参考：
剑指Offer面试题：32.数字在排序数组中出现的次数