Loading article…
 7 がターゲット値である乗法二分探索アルゴリズムの視覚化。 | |
| クラス | 検索アルゴリズム |
|---|---|
| データ構造 | 配列 |
| 最悪の場合の パフォーマンス | O (log n ) |
| 最高の パフォーマンス | お(1) |
| 平均的 なパフォーマンス | O (log n ) |
| 最悪の場合の 空間複雑度 | お(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 に進みます。
参照
- 二分探索木 – 根付き二分木データ構造
- バイナリツリーを格納する方法 – ツリーデータ構造の限定形式
- Ahnentafel – 個人の直系の祖先をリストするための系図番号システム
引用
- ^ Standish, Thomas A. (1980). 「第 4.2.2 章: 順序付きテーブル検索」.データ構造テクニック. Addison-Wesley. 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。