指数関数検索のしくみの悩み

Question

私は自分の試験と学習アルゴリズムを現時点で習得しています。私は線形、バイナリ、補間検索を理解し、指数関数的な検索を理解しようとしています。しかし、インターネット上の悪い情報源があり、説明がある場合は私にとって非常に複雑です..私はあなたがアルゴリズムを明確にできることを願っていますか？

編集（私のミスを修正するtryd）：

それでは、私たちは、配列を持っていると我々は、アレイに19を検索しましょう：

Index i 0 1 2 3 4 5 6 
     2 7 13 19 55 92 99 

我々は（の最初の範囲を見つけようその点、我々は、アレイを分割）

2^0 : i=1: A[1] > 19 
2^1 : i=2: A[2] > 19 
2^2 : i=4: A[4] < 19 

今、我々はにインデックスi=0から検索する必要があります知っています。

今、私たちが持っている現在のサブアレーが

Index i 0 1 2 3 
     2 7 13 19 

私たちは途中で分けるので、私たちは、アレイ

13 19 

を持つバイナリ検索で要素を見つける19

用のバイナリ検索を使用します途中でもう一度分けてください。 19は13より大きく、19は今配列の要素にすぎません。完了しました19

現在は正しいですか？

Answer 1

手順は、指数関数的に検索する段階でに増やす必要があります。

チェックされた要素（番号2^k）が検索する値よりも大きくなる（または等しい）まで、配列の第1要素、次に第2、第4、第8、第16などをチェックする必要があります。値を探索し、あなたが知っているこの瞬間に

は範囲2^(k-1)..2^kであり、この範囲指数ステージは範囲が急速に値を検索含む見つけることができます

ノートでバイナリ検索を開始します。

P.S. 0から始まる配列番号を調べる場合は、0番目のインデックスをチェックしてからインデックスシーケンス1,2,4,8,16を開始すると便利です。

Answer 2

指数検索は、無限の配列または未知のサイズの配列を検索するために使用されるアルゴリズムです。

た最初から最後まで、バイナリ検索を行う最初のステップは、あなたが定義することができます）値 2以上の最初の要素の位置を検索する）

1：これは、2つのステップがありますバイナリ検索の範囲。指数関数的な増加のため、指数関数的な検索と呼ばれます。