0

二分探索の多くの例を見てきましたが、それを最適化する方法がたくさんあるので、昨日講師がコードを書きました(このコードでは、最初のインデックスが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であると仮定しているので、講師は、要素が配列の中央部分にあるかどうかを毎回比較するのに時間を無駄にしないと言いました。また、要素が配列にない場合、インデックスはそれがどこにあるかを示します。だからそれは最適です、彼は正しいですか?つまり、ジョン・ベントレーからの多くの種類の二分探索(真珠のプログラミング)などを見たことがあります、そしてこのコードは本当に最適ですか?私の場合はパスカルで書かれていますが、言語依存しません。

4

1 に答える 1

1

それは本当にあなたが要素を見つけるかどうかに依存します。そうしないと、いくつかの比較が保存されます。最初の数ホップで要素を見つけることができれば、それ以降のすべての比較と計算の作業を節約できます。配列内のすべての値が異なる場合、早い段階で正しいインデックスに到達する可能性はかなり低いですが、同じ値を含む配列の広い範囲がある場合は、計算が変わります。

このアプローチは、他の方法ほど範囲を狭めることができないことも意味します-これは次のとおりです。

R:=m;

通常は

R:=m-1;

...それが大きな違いを生むことはめったにありませんが。

重要な点は、これによってアルゴリズムの全体的な複雑さが変わることはないということです。それでもO(log N)になります。

また、要素が配列にない場合、インデックスはそれがどこに配置されるかを示します。

あなたが平等をチェックするかどうかにかかわらず、それは真実です。私が見たすべてのバイナリ検索の実装は、その情報を提供します。

于 2012-10-10T05:50:03.270 に答える