剑指offer——38.数字在排序数组中出现的次数

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

分析：因为数组是排序的，我们很容易想到用二分查找算法。这里我们改进二分查找算法，如果找到了目标值，则它的左右两端都有可能会还有目标值，自然而然的想法是顺序扫描。时间复杂度为O(n)。与从头到尾扫描整个数组的时间复杂度一样，所以，我们改进二分法为确定重复出现的数字的第一个k和最后一个k的位置。

二分查找算法总是先拿数组中间的数字和k比较。大于小于情况不讨论了。如果等于的话，我们先判断这个数字是不是第一个k，如果中间数字的前面一个数字也是k，也就是说第一个k肯定在数组的前半段，下一轮我们仍然需要在数组的前半段查找。依次下去。我们就能找到第一个k了。

查找最后一个k的方法类似。代码如下：

public class Main {
public int GetNumberOfK(int[] array, int k) {
if (array == null || array.length == 0)
return 0;
int first = findFirst(array, k);
int last = findLast(array, k);
int len = 0;
if (first != -1 && last != -1)
len = last - first + 1;
return len;
}

public int findFirst(int[] array, int k) {
int start = 0;
int end = array.length - 1;
while (start <= end) {
int middle = (start + end) / 2;
if (array[middle] < k) {
start = middle + 1;
} else if (array[middle] > k) {
end = middle - 1;
} else if (array[middle] == k) {
if (middle > 0 && array[middle - 1] == k) {
end = middle - 1;
} else {
return middle;
}
}
}
return -1;
}

public int findLast(int[] array, int k) {
int start = 0;
int end = array.length - 1;
while (start <= end) {
int middle = (start + end) / 2;
if (array[middle] < k) {
start = middle + 1;
} else if (array[middle] > k) {
end = middle - 1;
} else if (array[middle] == k) {
if (middle < array.length-1 && array[middle + 1] == k) {
start = middle + 1;
} else {
return middle;
}
}
}
return -1;
}
}