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

题目

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

分析

由于数组是有序的，我们当然可以直接遍历一边数组，但是作为一个ACMer，你们能忍受这样的效率吗？

我不能，所以我选择下面这种方法；

由于数组有序，我们很快就能想到二分查找。以上面的数组为例，我们用两边二分查找分别找到最左边的3和最右边的3，然后他们之间的距离就是最后要输出的值。

接下来我们来分析以下如何用二分查找来找到数组中的第一个k。二分查找总是先拿数组中间的数字和k作比较。如果中间的数字比k大，那么k只可能出现在数组的前半段，之后我们只在数组的前半段查找就可以了。反之，同样。但是如果中间的数字和k相同，我们先判断它是否是第一个k，如果不是我们继续在数组的前半段查找。

全选

public class Solution {
    public static int GetFirstK(int[] array, int lenght, int begin, int end, int k) {
		if (end < begin)
			return -1;
		int midIndex = (end+begin)/2;
		int midData = array[midIndex];
		if (midData == k) {
			if ((midIndex > 0 && array[midIndex-1]!=k) || midIndex == 0)
				return midIndex;
			else
				end = midIndex-1;
		} else if (midData < k) {
			begin = midIndex+1;
		} else {
			end = midIndex-1;
		}
		return GetFirstK(array, lenght, begin, end, k);
	}
	
	public static int GetLastK(int[] array, int lenght, int begin, int end, int k) {
		if (end < begin)
			return -1;
		int midIndex = (end+begin)/2;
		int midData = array[midIndex];
		if (midData == k) {
			if ((midIndex < lenght-1 && array[midIndex+1]!=k) || midIndex == lenght-1)
				return midIndex;
			else
				begin = midIndex+1;
		} else if (midData < k) {
			begin = midIndex+1;
		} else {
			end = midIndex-1;
		}
		return GetLastK(array, lenght, begin, end, k);
	}
	
	public static int GetNumberOfK(int [] array , int k) {
		int lenght = array.length;
		int result = 0;
		if (array != null && lenght != 0) {
			int first = GetFirstK(array, lenght, 0, lenght-1, k);
			int last = GetLastK(array, lenght, 0, lenght-1, k);
			if (first != -1 && last != -1)
				result = last-first+1;
		}
		return result;
    }
}