2.6 問題2 回答

バイナリサーチ練習問題. 配列中に二度以上含まれる要素を一つ見つける.
再帰呼び出しする度に,要素毎にコピーした新しい配列を渡さなければならないので,
シーケンシャルなファイルにしか意味はない.
beginとendは配列に含まれる整数の範囲を示す.(STLと同じで,begin以上,end未満)

int Bsearch(int * xs, int n, int begin, int end){

	if(end-begin==1){
		return *xs;
	}
	int m = begin+(end-begin+1)/2;

	int * xss = new int[n];
	int * xsb = new int[n];
	int si=0;
	int bi=0;

	for(int i=0; i<n; i++){
		if(begin<=xs[i] && xs[i]<m){
			xss[si++] = xs[i];
		}else{
			xsb[bi++] = xs[i];
		}
	}
	int res;
	if(si > bi){
		res = Bsearch(xss,si,begin,m);
	}else{
		res = Bsearch(xsb,bi,m,end);
	}
	delete[] xss;
	delete[] xsb;
	return res;
}