二分探索の多くの例を見てきましたが、それを最適化する方法がたくさんあるので、昨日講師がコードを書きました(このコードでは、最初のインデックスが1から始まり、最後のインデックスがNであると仮定します。したがって、Nは配列の長さです。疑似コードのそれは次のようになります。
L:=1;
R:=N;
while( L<R)
{
m:=div(R+L,2);
if A[m]> x
{
L:=m+1;
}
else
{
R:=m;
}
}
ここでは配列がAであると仮定しているので、講師は、要素が配列の中央部分にあるかどうかを毎回比較するのに時間を無駄にしないと言いました。また、要素が配列にない場合、インデックスはそれがどこにあるかを示します。だからそれは最適です、彼は正しいですか?つまり、ジョン・ベントレーからの多くの種類の二分探索(真珠のプログラミング)などを見たことがあります、そしてこのコードは本当に最適ですか?私の場合はパスカルで書かれていますが、言語依存しません。