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回