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; }