リスト探索（list search）アルゴリズム

最も単純なリスト探索アルゴリズム

リストや配列に入ったデータに対する検索を行う
・各要素を単純に先頭から調べ（比較し）ていく
・見つかれば終了
・どんなリストでも適用可能

n個のデータから m個のデータを検索する場合
・時間計算量 … O(nm)
・空間計算量 … O(1)
・実行時間 … O(n)

n
・リスト上のアイテム数

---

具体例

下記のような7個のデータを持つリストがある

10	7	12	6	1	4	3

普通のケース ／ 要素1がどこにあるか、検索したい
・最初の要素である10を見る
・10は1ではないので、次の要素7を見る
・7は1ではないので、次の要素12を見る
・12は1ではないので、次の要素6を見る
・6は1ではないので、次の要素1を見る
・1を見つけることができた

最悪のケース ／ 要素3がどこにあるか、検索したい
・7個のデータ全てを見ないと、見つけることができない

n個のデータから1個のデータを検索する場合
・最悪O(n)の計算時間を要する

より洗練されたリスト探索アルゴリズム

データが多ければ多いほど線型探索よりも性能がよくなるが
・探索前にソートしておく必要がある
※同一データは無い前提

検索対象
・ソート済み配列
※大小関係を使用するため、「未ソートのリスト」や「大小関係の定義されない要素を含むリスト」には二分探索を適用することはできない

処理の流れ
・中央の値を見る
・検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断
・片側に存在しないことを確かめながら検索していく

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.、配列の中央位置を求める
・(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.、配列の中央位置を求める
・(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

データの全体の一番右側が29より小さい
・データが見つからないという結果になる

C.内挿探索

分布が偏っていないソートされた大きなリストでは二分探索よりも性能が良いが、最悪ケースでは O(n) となる