乗法二分探索
 | この記事は技術的すぎるため、ほとんどの読者には理解しにくいかもしれません。技術的な詳細を削除せずに、（2017年9月） |
 7 がターゲット値である乗法二分探索アルゴリズムの視覚化。 | |
| クラス | 検索アルゴリズム |
|---|---|
| データ構造 | 配列 |
| 最悪のパフォーマンス | O (log n ) |
| 最高のパフォーマンス | O (1) |
| 平均的なパフォーマンス | O (log n ) |
| 最悪の場合の空間複雑度 | O (1) |
| 最適 | はい |
コンピュータサイエンスにおいて、乗法二分探索は二分探索の一種で、通常の二分探索で使用されるソート順ではなく、配列内のキーの特定の順列を使用する。[ 1 ] 乗法二分探索は1980年にThomas Standishが初めて説明した。このアルゴリズムはもともと、効率的な除算やシフト演算を行わない小型コンピュータでの中点インデックス計算を簡略化するために提案された。現代のハードウェアでは、乗法二分探索のキャッシュフレンドリーな性質により、BツリーやB+ツリーの代わりとして、ブロック指向ストレージでのアウトオブコア探索に適している。最適なパフォーマンスを得るには、 BツリーまたはB+ツリーの分岐係数が、それが保存されているファイルシステムのブロックサイズと一致する必要がある。乗法二分探索で使用される順列は、ブロックサイズに関係なく、最初の（ルート）ブロックに最適な数のキーを配置する。
乗法二分探索は、一部の最適化コンパイラでswitch文を実装するために使用されます。[ 2 ] [ 3 ]
アルゴリズム
乗法二分探索は、並べ替えられた配列に対して実行されます。キーは、対応するバランス二分探索木のレベル順に格納されます。これにより、二分探索の最初のピボットが配列の最初の要素に配置されます。2番目のピボットは、次の2つの位置に配置されます。
値がA 0 ... A n −1であるn要素の配列Aとターゲット値Tが与えられた場合、次のサブルーチンは乗法バイナリ検索を使用してA内のTのインデックスを検索します。
- iを0に設定する
- i ≥ nの場合、検索は失敗して終了します。
- A i = Tの場合、検索は終了です。i を返します。
- A i > Tの場合、i を2× i + 1 に設定し、手順 2 に進みます。
- A i < Tの場合、i を2× i + 2 に設定し、手順 2 に進みます。
参照
- 二分探索木 – 根付き二分木データ構造
- 二分木を格納する方法 – 木データ構造の限定形式
- アーネンターフェル – 直系の祖先を列挙するための系図番号システム
引用
- ^スタンディッシュ、トーマス・A. (1980). 「第4.2.2章 順序付きテーブル検索」.データ構造テクニック. アディソン・ウェスレー. pp. 136–141 . ISBN 978-0201072563。
- ^ Sayle, Roger A. (2008年6月17日). 「スーパーオプティマイザーによる多分岐コード生成の分析」(PDF) . GCC開発者サミット議事録: 103–116 . 2017年3月4日閲覧。
- ^ Spuler, David A. (1994年1月).静的探索問題としての多分岐文に対するコンパイラコード生成（技術レポート）. オーストラリア、ジェームズクック大学、コンピュータサイエンス学部、94/03.
