【题目】
题目来源于头条面试的一道算法题，如下：
给一个排序好的数组，里面有重复元素。
例子：[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;
}
}
