剣指offer 35--数字が配列ソートに現れる回数

一、テーマ
タイトル:数値の統計:ソート配列に表示される回数.
二、例を挙げる
例えば、ソート配列｛1,2,3,3,3,3,4,5｝と数字3を入力し、この配列に3が4回出現したため、4を出力する.
三、思想
(1)この問題を見る第一の考え方は,配列が短い場合は問題ないが,配列が長い場合は実行効率の問題が生じるように遍歴的に検索することである.
(2)2つ目は、半分以上の効率を向上させるために、data[middle]==kが見つかるまで2点検索を使用することです.つまり、kがこの範囲内で、この2辺のkの個数を統計すればいいということです.
四、プログラム

package   offer;
/*  ：      ：           */
public class Test38 {
	
	//   k   ，      k       
	public static void findRange(int data[], int start, int end, int k){
		//       
		if(data == null || start >= end || k > data[end]){
			System.out.println("Error");
		}
		
		int middle = (start + end)/2;
		if(data[middle] == k){
			System.out.println(findNumber(data, start, end, middle, k));
		}else if(middle != k){
			findRange(data, start, middle, k);
			findRange(data, middle+1, end, k);
		}
		
	}
	
	//             k      
	public static int findNumber(int data[], int start, int end, int middle, int k){
		int result = 0;
		
		int middleRight = middle;
		int middleLeft = middle;
		
		//              ，        
		if(data[end] == k){
			result++;
		}
		if(data[start] == k){
			result++;
		}
		
		//         
		while(data[middleRight] == k && middleRight != end){

			middleRight++;
			result++;
		}
		
		//     
		while(data[middleLeft] == k && middleLeft != start){

			middleLeft--;
			result++;
		}
		
		return result - 1;
	}
	
	public static void main(String args[]){
        //              
        int[] data1 = {1, 2, 3, 3, 3, 3, 4, 5};
        findRange(data1, 0, data1.length - 1, 3); // 4
        
        //              
        int[] data2 = {3, 3, 3, 3, 4, 5};
        findRange(data2, 0, data2.length - 1, 3); // 4

        //              
        int[] data3 = {1, 2, 3, 3, 3, 3};
        findRange(data3, 0, data3.length - 1, 3); // 4

	}
}

五、収穫
個数を集計するときは両方の状況に注意し、条件の制約により集計できない場合があり、特殊な処理が必要となります.