バイナリ検索パターン実装の詳細/利用状況に関する質問

Question

次SO urlはランダウの記号のためのいくつかの良い実例を提供しています。

What does O(log n) mean exactly?

私は、バイナリサーチのために提供される次の例では、特に興味：

"O（log n）：人の名前を指定すると、あなたがまだ検索していない本の部分の半分についてランダムな点を選んで電話番号を探し、その人の名前がその時点で、本の一部を半分くらいまで繰り返して、人の名前があります。 （これは、人の名前のバイナリ検索です。）」

は私が不明確だこのことについていくつかのことがあります。正確な途中で検索して

• は教科書バイナリ検索開始をいは、配列の偶数個の項目がある場合、テキストブックバイナリ検索アルゴリズムは、下位項目または上位項目をランダムに選択する必要がありますか？

• テキストブックバイナリ検索で特定のデータポイント効率を上げるためにデータポイントのクラスタ化されたグループを検索するのか、またはバイナリ検索パターンでこれらのアプローチの1つ？

• バイナリ検索は、ソート済み配列またはソート済み配列のどちらにも適用できますか？または、バイナリ検索を実行する前に、配列をプログラムでソートすることをお勧めしますか？

Answer 1

この例では正しく説明されていないことがいくつかあります。まず、辞書という名前で検索しているとします。たとえば、「John」を検索しているとします。 （n/2）番目のページには、文字L（例：ページX）で始まる名前が付けられます。だから、あなたはこのページから始まるものすべてを無視し、このページとそれ以上のものはあなたが探しているものを持つことができないことを知っているからです。今度は、検索セットがページ1からページXに検索されるようになります。ページを選択するたびに、検索セットのn/2項目を無視する同じ手順を繰り返します。私は与えられたのだ説明からそう

、：

1）nが偶数/奇数の場合、ちょうどあなたがn/2で何を得る選びます。あなたは、次の反復でページ1を（n/2）-1（または）ページ（n/2）+1からnと考えるかどちらかです。したがって、ここで要素をスキップするリスクはありません。

2.）繰り返しごとに、検索セット全体を検討します。反復iからi + 1までの検索セットの違いは、 の要素数が半減したことです。

3）BSの前提条件の1つは、ソートされたアイテムのリストを検討する必要があることです。それが私の説明で辞書を使った理由です。

そして、この操作がO（logn）である理由は、項目のリストを毎回半分に減らすためです。あなたがリストに32項目を持っていると想像してみてください。ここで答えを見つけるために必要な反復の回数は5回です（32回目は最初の反復で16回、2回目の反復では8回に減らされます）。表示されているように、32と5の関係はです。log 32（base 2）= 5