數字在排序數組中出現的次數 java

題目：統計一個數字在排序數組中出現的次數。例如輸入排序數組{1,2,3,3,3,3,4,5}和數字3，由于3在這個數組中出現了4次，是以輸出4.

思路：

用二分查找，分别找出第一個3，和最後一個3的位置，然後計算個數。

時間複雜度O（logn）

代碼：

package niuke.easy;

public class GetNumberOfK {

	public static void main(String[] args) {

	}

	/**
	 * 題目描述 統計一個數字在排序數組中出現的次數。 <br/>
	 * 解題思路 數組是排序的，是以重複出現的數字是相鄰排列的。 用二分查找算法，找到第一次出現的位置，和 最後一次出現的位置。
	 * 判斷第一次出現的位置條件為：目前數字的前一個是否與之相等，若是則繼續查找，否則該位置就是第一次出現的位置。
	 * 判斷最後一次出現的位置條件為：目前數字的後一個是否與之相等，若是則繼續查找，否則該位置就是最後一次出現的位置。 出現的次數= last -
	 * first +1
	 * 時間複雜度：O(logn)
	 * 
	 * @param array
	 * @param k
	 * @return
	 */
	public int GetNumberOfK(int[] array, int k) {
		int result = 0;
		if (array == null || array.length == 0) {
			return 0;
		}

		int start = 0, end = array.length - 1;

		int firstIndex = getFirstIndex(array, start, end, k);
		int lastIndex = getLastIndex(array, start, end, k);

		if (firstIndex > -1 && lastIndex > -1) {
			result = lastIndex - firstIndex + 1;
		}

		return result;
	}

	private int getLastIndex(int[] array, int start, int end, int k) {
		if (start > end) {
			return -1;
		}

		int midIndex = (start + end) / 2;
		int midData = array[midIndex];

		if (midData == k) {
			if (midIndex < array.length - 1 && array[midIndex + 1] != k
					|| midIndex == array.length - 1) {
				return midIndex;
			} else {
				start = midIndex + 1;
			}
		} else if (midData > k) {
			end = midIndex - 1;
		} else {
			start = midIndex + 1;
		}

		return getLastIndex(array, start, end, k);
	}

	private int getFirstIndex(int[] array, int start, int end, int k) {
		if (start > end) {
			return -1;
		}

		int midIndex = (start + end) / 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) {
			end = midIndex - 1;
		} else {
			start = midIndex + 1;
		}

		return getFirstIndex(array, start, end, k);
	}

}