仕事で二分探索というアルゴリズムを使っているところがあったので勉強を兼ねて調べてみた。
アルゴリズムについて
- あるデータを特定するときに、データ数の真ん中から検索をしていく。
- その中間値が調べたいデータより大きい値・小さい値・同じ値かを調べる
- 大きい場合は中間値より大きい値を調べに行く。その際に、
（調べた番号の値＋調べていない一番大きい番号）/ 2の値を調べていく。
小さい場合は中間値より大きい値を調べに行く。その際に、（調べた番号の値+調べていない一番小さい番号）/ 2の値を調べていく。 - 2．と3．を繰り返し、同じ値になるまで検索していく。
調べ方については実際に表にして考えてみると分かりやすい。
そして、なぜソートされていなければならないかもわかりやすくなる。
中間値より小さいデータを調べに行く場合
たとえば、日付のデータが並んでいる場合に2021-05-06を探しに行くことを考える。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 2021-05-05 | 2021-05-06 | 2021-05-07 | 2021-05-08 | 2021-05-09 | 2021-05-10 | 2021-05-11 |
1回目
最初は中間のデータを取得する。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 2021-05-05 | 2021-05-06 | 2021-05-07 | 2021-05-08 | 2021-05-09 | 2021-05-10 | 2021-05-11 |
| ∩('ω') |
そしてこの値が調べたいデータより高い・小さいかを判断する。
今回であれば、2021-05-06よりは大きいので、中間値より大きい5～8のデータは必ず2022-05-06ではないと言える。
2回目
次はデータ最小値の1と調べた4の中間値、(1 + 4) / 2 =2 or 3を調べる。
今回は切捨で調べることにして、2のデータを確認する。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 2021-05-05 | 2021-05-06 | 2021-05-07 | 2021-05-08 | 2021-05-09 | 2021-05-10 | 2021-05-11 |
| ∩('ω') |
そしてこの値が調べたいデータより高い・小さいかを判断する。
今回等しいので、これで検索は終了になる。
中間値より大きいデータを調べに行く場合
今度は中間値より大きいに2021-05-10を探しに行くことを考える。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 2021-05-05 | 2021-05-06 | 2021-05-07 | 2021-05-08 | 2021-05-09 | 2021-05-10 | 2021-05-11 |
1回目
最初は中間のデータを取得する。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 2021-05-05 | 2021-05-06 | 2021-05-07 | 2021-05-08 | 2021-05-09 | 2021-05-10 | 2021-05-11 |
| ∩('ω') |
そしてこの値が調べたいデータより高い・小さいかを判断する。
今回であれば、2021-05-06よりは小さいので、中間値より小さい1～4のデータは必ず2022-05-06ではないと言える。
2回目
次はデータ最大値の7と調べた4の中間値、(7 + 4) / 2 =5 or 6のデータを調べる。
今回は切り捨てで考えて、5のデータを調べることにしよう。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 2021-05-05 | 2021-05-06 | 2021-05-07 | 2021-05-08 | 2021-05-09 | 2021-05-10 | 2021-05-11 |
| ∩('ω') |
そしてこの値が調べたいデータより高い・小さいかを判断する。
今回であれば、2021-05-06よりは小さいので、中間値より小さい5のデータは必ず2022-05-06ではないと言える。
3回目
次はデータ最大値の7と調べた5の中間値、(7 + 5) / 2 =6のデータを調べる。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 2021-05-05 | 2021-05-06 | 2021-05-07 | 2021-05-08 | 2021-05-09 | 2021-05-10 | 2021-05-11 |
| ∩('ω') |
そしてこの値が調べたいデータより高い・小さいかを判断する。
今回等しいので、これで検索は終了になる。
なぜソートしていないとダメなのか？
先ほどの表をバラバラに並べて考えてみよう。
ここから2022-05-06を取ることを考えてみる。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 2021-05-05 | 2021-05-07 | 2021-05-08 | 2021-05-11 | 2021-05-06 | 2021-05-09 | 2021-05-10 |
結論：無限ループになってたどり着けなくなる時がある
最初は中間のデータを取得する。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|
| 2021-05-05 | 2021-05-07 | 2021-05-08 | 2021-05-11 | 2021-05-06 | 2021-05-09 | 2021-05-10 |
| ∩('ω') |
そしてこの値が調べたいデータより高い・小さいかを判断する。
今回の中間値は2022-05-11なので、それより小さい。
しかし、実際は2022-05-06は5番目に存在する。
そうなるとどうなってしまうかというと、ロジック通りに検索すると永遠に2022-05-06にたどり着けなくなってしまう。
従って、「調べたいデータがソート順に並んでいる」ことが前提条件になってしまう。