カテゴリー:
探索アルゴリズム
閲覧数:366 配信日:2016-09-12 10:01
より洗練されたリスト探索アルゴリズム
データが多ければ多いほど線型探索よりも性能がよくなるが
・探索前にソートしておく必要がある
※同一データは無い前提
検索対象
・ソート済み配列
※大小関係を使用するため、「未ソートのリスト」や「大小関係の定義されない要素を含むリスト」には二分探索を適用することはできない
処理の流れ
・中央の値を見る
・検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断
・片側に存在しないことを確かめながら検索していく
n個のデータがある場合、
・時間計算量 … O(log2 n)
・実行時間 … O(log n)
n個のデータの「中央の値」を見ることで、
・1回の操作でn/2個程度（奇数の場合は(n-1)/2個、偶数の場合はn/2個または(n/2)-1個）の要素を無視することができる
データが見つかる具体例
下記配列から25を探し出す
・同一のデータは無い
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| データ | 1 | 3 | 4 | 11 | 12 | 13 | 17 | 22 | 25 | 28 |
・(1+10)/2=5
（端数は切捨、切上のどちらでもいいが、ここは切捨とする。以下同じ）
・位置5のデータは12なので「×」
・位置1～4まではデータを調べなくても「×」と分かる。※予め昇順ソートしているため
2-1.残りの配列の中央位置を求める
・位置6～10の中央位置は、(6+10)/2=8
・位置8のデータは22なので「×」
・位置6～7まではデータを調べなくても「×」と分かる。※予め昇順ソートしているため
2-2.残りの配列の中央位置を求める
・位置9～10の中央の位置は、(9+10)/2=9
（端数は切捨、切上のどちらでもいいが、ここは切捨とする。以下同じ）
・位置9のデータは25なので目的のデータが見つかった
・位置10は調べていないが、同一のデータは存在しないという想定なので「×」としてよい
データが見つからない具体例1
下記配列から4を探し出す
・同一のデータは無い
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| データ | 1 | 3 | 5 | 11 | 12 | 13 | 17 | 22 | 25 | 28 |
・(1+10)/2=5
・位置5のデータは12なので「×」
・位置6～10まではデータを調べなくても「×」と分かる。※予め昇順ソートしているため
2-1.残りの配列の中央位置を求める
・位置1～4の中央の位置は、(1+4)/2=2
・位置2のデータは3なので「×」
・位置1のデータは1なので「×」
2-2.残りの配列の中央位置を求める
・位置3～4の中央の位置は、(3+4)/2=3
・位置3のデータは5なので「×」
・以上でデータが見つからないという結果になる
データが見つからない具体例2
下記配列から29を探し出す
・同一のデータは無い
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| データ | 1 | 3 | 5 | 11 | 12 | 13 | 17 | 22 | 25 | 28 |
・データが見つからないという結果になる