＜集大成＞アルゴリズム大辞典

＜集大成＞アルゴリズ ..

310:デフォルトの名無しさん
07/11/24 23:27:09
何がやりたいのかわからんので、
エスパーで問題を考えて回答しよう。

入力
*X;(1,2,4,4,4,5,6,7);//ソート済み配列,長さO(n)
Pivot=4;//比較する値
Begin=0;//探索範囲？
End==7;//
出力
(2,5);//(1,2),(4,4,4),(5,6,7)と分けたときの4と5のインデックス

アルゴリズム
B=Begin;E=End;
while(E-B&g;1)
if(X[(B+E)/2]>Pivot)
　　E=(B+E)/2;
else if(X[(B+E)/2]<Pivot)
　　B=(B+E)/2;
else
{　　N=(B+E)/2; break; }

以降はBとN間、NとE間の境界を通常の二分探索で見つける。
比較回数の最悪は明らかに1回目の比較でbreakして全体の1/2のサイズの二分探索を二回行わなければならないときで、
1+2(logn-1)=2logn-1回

次ページ

続きを表示

1を表示