ソート配列に数値が表示される回数(Java)


タイトル:
ソート配列に表示される数値の回数を統計します.例えばソート配列{1,2,3,3,3,3,4,5}と数字3を入力し,3がこの配列に4回出現したため4を出力する.
考え方:
第1の解法:蛮力法、配列を順番に遍歴して、数字の3の出現の回数を統計して、しかしこの時テーマの中で与える秩序を利用していないで、だから時間は複雑で大きくて、要求に合いません.
第2の解法:二分探索の思想(時間複雑度log(n))を利用して問題を解決する.まず、配列中の3が現れる最初の位置first 3を見つけてから、配列中の3が最後に現れる位置end 3を見つけて、first 3-end 3+1は数字3が現れる回数です.
コード実装:
public class Main {

	//     k   
	private int getFirstK(int nums[], int k, int start, int end){
		if(start > end){
			return -1;
		}
		int middleIndex = (start + end) /2;
		int middleData = nums[middleIndex];
		if(middleData == k){
			//       k     :  middleIndex=0;  middleIndex > 0  middleIndex-1       k
			if((middleIndex > 0 && nums[middleIndex-1]!=k) || middleIndex == 0){
				return middleIndex;
			}else{
				end = middleIndex -1;
			}
		}else if(middleData > k){
			end = middleIndex - 1;
		}else{
			start = middleIndex + 1;
		}
		return getFirstK(nums, k, start, end);
	}
	
	//      k   
	private int getLastK(int nums[], int k, int start, int end){
		if(start > end){
			return -1;
		}
		int middleIndex = (start + end) / 2;
		int middleData = nums[middleIndex];
		if(middleData == k){
			//        k     :  middleIndex=  -1;  middleIndex < len-1  middleIndex+1       k
			if((middleIndex < nums.length -1 && nums[middleIndex + 1] != k) || middleIndex == nums.length -1){
				return middleIndex;
			}else{
				start = middleIndex + 1;
			}
		}else if(middleData < k){
			start = middleIndex + 1;
		}else{
			end = middleIndex -1;
		}
		return getLastK(nums, k, start, end);
	}
	
	public int getNumberOfK(int nums[], int k){
		int number = 0;
		int len = nums.length;
		if(nums != null && len > 0){
			int firstK = getFirstK(nums, k, 0, len-1);
			int lastK = getLastK(nums, k, 0, len-1);
			if(firstK > -1 && lastK > -1){
				number = lastK - firstK + 1;
			}
		}
		return number;
	}
	
	public static void main(String[] args) {
		Main m1 = new Main();
		int nums[] = new int[]{1, 2, 3, 3, 3, 3, 4, 5};
		int count = m1.getNumberOfK(nums, 3);
		System.out.println(count);
	}
}