探索アルゴリズムとは？線形探索・二分探索・ハッシュ探索・DFS・BFSを基礎から理解しよう
はじめに
プログラムでは、大量のデータの中から目的のデータを探す処理が頻繁に行われます。
例えば、
[12][7][25][3][18]
というデータから、
18
を探すような処理です。
このような、
複数のデータの中から目的のデータを見つける処理
を**探索（Search）**と呼びます。
探索にはさまざまな方法があり、データの状態やデータ構造によって適したアルゴリズムが異なります。
この記事では、
探索アルゴリズム
│
├─ 線形探索
├─ 二分探索
├─ ハッシュ探索
├─ 二分探索木による探索
├─ 深さ優先探索（DFS）
└─ 幅優先探索（BFS）
を中心に学んでいきます。
1. 探索アルゴリズムとは
**探索アルゴリズム（Search Algorithm）**とは、
データの集合から、目的のデータを探し出すための手順
です。
例えば、
[8][3][12][5][9]
から5を探すとします。
人間なら、
8 → 違う
3 → 違う
12 → 違う
5 → 発見
と探すことができます。
コンピュータでも同じように、決められた手順に従ってデータを探します。
その「探し方」が探索アルゴリズムです。
2. 探索方法によって速さが違う
例えば100万件のデータから1件を探すとします。
毎回、
1件目
↓
2件目
↓
3件目
↓
...
と確認していたら、目的のデータによっては非常に多くの比較が必要になります。
一方、
半分に絞る
↓
さらに半分
↓
さらに半分
と探索範囲を減らせれば、比較回数を大幅に減らせます。
そのため、
どの探索アルゴリズムを使うか
はプログラムの性能に大きく影響します。
3. 線形探索とは
最も基本的な探索方法が**線形探索（Linear Search）**です。
**逐次探索（Sequential Search）**とも呼ばれます。
線形探索では、
データを先頭から一つずつ順番に調べる
ことで目的のデータを探します。
例えば、
[12][7][25][3][18]
から3を探してみましょう。
12
↓
違う
7
↓
違う
25
↓
違う
3
↓
発見
となります。
4. 線形探索の処理
疑似コードで考えると、
for i = 0 から n - 1
if data[i] == 探索値
発見
という非常にシンプルな処理です。
目的のデータが、
[3][12][7][25][18]
↑
のように最初にあれば、1回の比較で見つかります。
しかし、
[12][7][25][18][3]
↑
のように最後にあれば、すべてのデータを調べる必要があります。
5. 線形探索の計算量
データ数をnとすると、最悪の場合、
n個すべてを調べる
必要があります。
そのため、線形探索の時間計算量は、
O(n)
です。
データ数が2倍になれば、最悪の場合に調べる回数もおおよそ2倍になります。
6. 線形探索のメリット
線形探索には大きなメリットがあります。
それは、
データが並び替えられていなくても使える
ことです。
例えば、
[53][2][91][18][7][34]
のようにバラバラでも問題ありません。
先頭から順番に調べれば探索できます。
そのため、
実装が簡単
+
事前のソートが不要
という特徴があります。
7. 線形探索のデメリット
一方、データが大量になると効率が悪くなる場合があります。
例えば100万件のデータから最後のデータを探す場合、最悪100万件を確認することになります。
O(n)
なので、データ量の増加とともに探索時間も増加します。
そこで、データが整列されている場合に利用できるのが二分探索です。
8. 二分探索とは
**二分探索（Binary Search）**とは、
探索範囲を半分ずつに絞り込んで目的のデータを探す方法
です。
ただし、重要な条件があります。
探索対象のデータがキーの大小順に整列されている必要があります。
例えば、
[2][5][8][12][16][23][30]
から23を探してみましょう。
9. 二分探索の流れ
まず中央のデータを調べます。
[2][5][8][12][16][23][30]
↑
12
探しているのは23です。
23 > 12
なので、12より左側を調べる必要はありません。
[16][23][30]
だけに絞ります。
次に中央を確認します。
[16][23][30]
↑
23
見つかりました。
10. なぜ半分を捨てられるの？
二分探索で重要なのが、データが整列されていることです。
例えば、
[2][5][8][12][16][23][30]
で中央が12だったとします。
探している値が23なら、
23 > 12
です。
データは昇順なので、12より左側には23が存在しないことが分かります。
そのため、
[2][5][8]
をまとめて探索対象から除外できます。
これが二分探索が高速な理由です。
11. 二分探索の計算量
二分探索では、
n
↓
n / 2
↓
n / 4
↓
n / 8
↓
...
と探索範囲を半分ずつ減らしていきます。
そのため時間計算量は、
O(log n)
です。
例えば、およそ100万件の整列済みデータでも、理論上は20回程度の比較で探索範囲を絞り込めます。
2^20 ≒ 1,000,000
だからです。
12. 線形探索と二分探索
整理すると、
| 項目 | 線形探索 | 二分探索 |
|---|---|---|
| 探し方 | 先頭から順番 | 半分ずつ絞る |
| 整列 | 不要 | 必要 |
| 計算量 | O(n) | O(log n) |
| 実装 | シンプル | やや複雑 |
重要なのは、
二分探索の方が速い
だけで覚えないことです。
二分探索を使うためには、
探索対象が適切に整列されている
という前提があります。
13. 二分探索の疑似コード
基本的な考え方は、
left = 0
right = データ数 - 1
while left <= right
mid = 中央位置
if data[mid] == 探索値
発見
else if data[mid] < 探索値
left = mid + 1
else
right = mid - 1
です。
探索値 > 中央値
→ 右側
探索値 < 中央値
→ 左側
と範囲を絞っていきます。
14. 番兵法とは
線形探索を効率よく実装する方法として**番兵法（Sentinel Method）**があります。
通常の線形探索では、
目的の値か？
配列の最後まで来たか？
という複数の条件を確認しながら探索することがあります。
番兵法では、探索対象の末尾などに探索したい値と同じ値を番兵として置くことで、終了判定を単純化します。
例えば8を探すなら、
[3][5][2][7][8]
↑
番兵
のようにします。
これによって探索中は、
値が8か？
という判定に集中できます。
見つかった8が、
本来のデータ
なのか、
番兵
なのかを最後に判定します。
15. ハッシュ探索とは
次に**ハッシュ（Hash）**を利用した探索です。
ハッシュ探索では、
キーから格納場所を計算し、その場所へ直接アクセスする
という考え方を利用します。
例えば、
社員番号 12345
というキーから、
ハッシュ関数
↓
格納場所 5
を求め、
0 1 2 3 4 5 6
↑
データ
のようにアクセスします。
16. ハッシュ関数とは
キーから格納場所を計算するための関数を**ハッシュ関数（Hash Function）**と呼びます。
例えば単純な例として、
ハッシュ値
=
キー mod 10
とします。
キーが、
123
なら、
123 mod 10
=
3
なので、
位置3
へ格納します。
17. ハッシュ表とは
ハッシュ関数によって求めた位置へデータを格納するための表を**ハッシュ表（Hash Table）**と呼びます。
例えば、
キー ハッシュ値
21 → 1
32 → 2
44 → 4
なら、
0
1 → 21
2 → 32
3
4 → 44
のように格納できます。
探索するときもキーから同じハッシュ値を求めれば、格納位置を特定できます。
18. ハッシュ探索の計算量
ハッシュ表が適切に構成されていれば、探索は平均的に、
O(1)
で行えます。
つまり、データ数が増えてもキーから格納場所を直接求められるため、非常に高速な探索が期待できます。
ただし、
常にO(1)になるわけではありません。
その理由が衝突です。
19. 衝突とは
異なるキーから同じハッシュ値が求められることがあります。
例えば、
ハッシュ値
=
キー mod 10
なら、
21 mod 10 = 1
31 mod 10 = 1
となります。
21 → 位置1
31 → 位置1
となり、同じ場所を使おうとしています。
この現象を衝突（Collision）またはシノニムと呼びます。
20. チェイン法
衝突を解決する代表的な方法の一つが**チェイン法（Chaining）**です。
同じハッシュ値になったデータを、連結リストなどを使ってつなぎます。
例えば、
ハッシュ値1
↓
[21] → [31] → [41] → NULL
のようにします。
ここで以前学んだ連結リストが登場します。
ハッシュ表
+
連結リスト
=
チェイン法
というつながりです。
21. オープンアドレス法
もう一つの代表的な衝突解決方法が**オープンアドレス法（Open Addressing）**です。
衝突した場合に、
ハッシュ表の別の空いている場所を探して格納する
方法です。
例えば、
21 → 位置1
に格納済みで、
31 → 位置1
となった場合、
位置1 → 使用中
位置2 → 空き
なら、
31 → 位置2
へ格納します。
22. 線形探査法
オープンアドレス法の代表的な方法が**線形探査法（Linear Probing）**です。
衝突したら、
次
↓
次
↓
次
と順番に空いている場所を探します。
例えば、
位置1 → 使用中
位置2 → 使用中
位置3 → 空き
なら、
位置3
へ格納します。
「線形探索」と「線形探査法」は名前が似ていますが別物なので注意しましょう。
23. ハッシュ探索の注意点
ハッシュ表は高速ですが、衝突が大量に発生すると性能が低下します。
例えばチェイン法で、
位置1
↓
[A] → [B] → [C] → [D] → [E]
のように大量のデータが同じ場所へ集中すると、その中を順番に探す必要があります。
そのため、
ハッシュ関数によってデータを適切に分散させる
ことが重要です。
24. 二分探索木による探索
前回学んだ**二分探索木（Binary Search Tree）**も探索に利用できます。
例えば、
8
/ \
4 12
/ \ / \
2 6 10 14
では、
左 < 親 < 右
という関係があります。
10を探すなら、
10 > 8
→ 右
10 < 12
→ 左
10 = 10
→ 発見
となります。
25. 二分探索と二分探索木は別物
名前が非常に似ていますが、
二分探索と二分探索木は別物です。
二分探索は、
整列された配列など
↓
中央の要素と比較
↓
探索範囲を半分にする
アルゴリズムです。
一方、二分探索木は、
親
/ \
小さい 大きい
というルールで構成されたデータ構造です。
整理すると、
二分探索
→ 探索アルゴリズム
二分探索木
→ データ構造
です。
26. 二分探索木の計算量
バランスのよい二分探索木なら、探索はおおよそ、
O(log n)
です。
しかし、
1
\
2
\
3
\
4
のように偏ると、
1 → 2 → 3 → 4
と順番に調べることになり、最悪、
O(n)
になります。
そのため前回学んだAVL木などのバランス木では、木の高さを抑えることで探索性能を保ちます。
27. グラフや木の探索
ここまでは、
配列
ハッシュ表
二分探索木
などから特定のデータを探す方法を見てきました。
一方、木構造やグラフでは、
ノード同士のつながりをたどりながら探索する
方法があります。
代表的なのが、
深さ優先探索
幅優先探索
です。
28. 深さ優先探索とは
**深さ優先探索（Depth-First Search：DFS）**とは、
一つの方向へできるだけ深く進み、行き止まりになったら戻る探索方法
です。
例えば、
A
/ \
B C
/ \ \
D E F
という木を考えます。
左側から探索すると、
A
↓
B
↓
D
と深い方向へ進みます。
Dから先へ進めなければ戻り、
E
を探索します。
29. DFSとスタック
DFSでは、
どこまで戻ればよいのか
を覚えておく必要があります。
そこで利用できるのがスタックです。
DFS
↓
深く進む
↓
戻る場所を保存
↓
LIFO
↓
スタック
という関係があります。
また、再帰処理を利用してDFSを実装することもできます。
再帰処理でも内部的には呼出し情報がスタックへ積まれます。
そのため、
🍯 DFS = スタック・再帰
と関連付けて覚えると分かりやすいです。
30. 幅優先探索とは
**幅優先探索（Breadth-First Search：BFS）**とは、
現在のノードから近いノードを順番に探索する方法
です。
同じ木なら、
A
/ \
B C
/ \ \
D E F
まず、
A
を調べます。
次に、
B → C
を調べます。
その次に、
D → E → F
を調べます。
つまり、
A
↓
B → C
↓
D → E → F
と、階層ごとに探索していきます。
31. BFSとキュー
BFSでは、
先に見つけたノードから順番に探索する
必要があります。
そこで利用できるのがキューです。
例えばAを調べると、
B
C
が見つかるのでキューへ追加します。
Queue
[B][C]
Bを取り出して処理すると、DとEを追加します。
Queue
[C][D][E]
次にCを処理します。
このように、
先に追加したノード
↓
先に処理
となるため、FIFOのキューと相性がよいのです。
🍯 BFS = キュー
と覚えておきましょう。
32. DFSとBFSの違い
整理すると、
| 項目 | DFS | BFS |
|---|---|---|
| 正式名称 | Depth-First Search | Breadth-First Search |
| 日本語 | 深さ優先探索 | 幅優先探索 |
| 探し方 | 深く進む | 近いところから広げる |
| 主に使う構造 | スタック | キュー |
| 再帰 | 利用しやすい | 通常はキューを利用 |
イメージとしては、
DFS
↓
↓
↓
深く！
BFS
→ → →
横に広く！
です。
33. BFSと最短経路
BFSには重要な特徴があります。
各辺の重みを考えないグラフでは、BFSを使うことで始点から各ノードまでの辺の本数が最小となる経路を求められます。
例えば、
A ─ B ─ D
│
C ─ E
のようなグラフでAから探索すると、
距離0
A
距離1
B・C
距離2
D・E
というように、近いノードから順番に探索できます。
そのため、重みのないグラフの最短経路探索に利用できます。
34. 重み付きグラフではどうする？
例えば、
A ─5─ B
│
2
│
C
のように、辺ごとに、
距離
時間
料金
などの重みが付いている場合があります。
このようなグラフを重み付きグラフと呼びます。
単純なBFSでは、辺の本数は比較できても、それぞれ異なる重みを考慮した最短経路を一般には求められません。
そこで利用される代表的なアルゴリズムが、
ダイクストラ法（Dijkstra's Algorithm）
です。
35. ダイクストラ法とは
ダイクストラ法は、
辺の重みが負でないグラフで、始点から各頂点までの最短経路を求める代表的なアルゴリズム
です。
例えば、
A ─10─ B
│ /
2 3
│ /
C
というグラフを考えます。
AからBへ直接進むと、
10
かかります。
一方、
A → C → B
なら、
2 + 3 = 5
です。
したがって、
A → C → B
の方が短い経路になります。
36. ダイクストラ法の基本的な考え方
ダイクストラ法では、
始点からの現在の最短距離
を管理します。
そして、
まだ確定していない頂点の中から、始点からの距離が最も小さい頂点を選ぶ
という処理を繰り返します。
概念的には、
始点
↓
一番近い頂点を確定
↓
そこから行ける頂点の距離を更新
↓
次に近い頂点を確定
↓
...
という流れです。
37. ダイクストラ法の注意点
ダイクストラ法には重要な条件があります。
負の重みを持つ辺が存在するグラフには、そのまま適用できません。
例えば、
A → B 重み5
A → C 重み10
C → B 重み-20
のような場合です。
ダイクストラ法では一度最短距離として確定した頂点について、後からさらに短い経路が現れないことを前提にしています。
負の辺があると、この前提が崩れる可能性があります。
38. 探索アルゴリズムを比較しよう
ここまでの代表的な探索方法を整理します。
| 探索方法 | 主な対象・前提 | 特徴 |
|---|---|---|
| 線形探索 | 一般的な列 | 先頭から順番に調べる |
| 二分探索 | 整列済みデータ | 半分ずつ探索範囲を絞る |
| ハッシュ探索 | ハッシュ表 | キーから格納場所を計算 |
| 二分探索木 | BST | 大小関係を利用してたどる |
| DFS | 木・グラフ | 深い方向を優先 |
| BFS | 木・グラフ | 近いノードから探索 |
| ダイクストラ法 | 非負の重み付きグラフ | 最短経路を求める |
それぞれ、
何を探すのか
+
データがどう管理されているのか
によって使い分けます。
39. 計算量を比較する
基本的な探索について整理すると、
| 探索 | 計算量の目安 |
|---|---|
| 線形探索 | O(n) |
| 二分探索 | O(log n) |
| ハッシュ探索 | 平均O(1) |
| バランスのよい二分探索木 | O(log n) |
| 偏った二分探索木 | 最悪O(n) |
ただし、
計算量だけを見てアルゴリズムを選べばよいわけではありません。
例えば二分探索には、
データが整列されている
という前提があります。
ハッシュ探索では、
ハッシュ表を用意する
衝突を処理する
必要があります。
それぞれの前提条件まで理解することが重要です。
40. 応用情報で押さえたいポイント
まず、
線形探索
→ 先頭から順番
→ O(n)
です。
二分探索は、
整列済みデータ
↓
中央と比較
↓
探索範囲を半分
↓
O(log n)
です。
ハッシュ探索は、
キー
↓
ハッシュ関数
↓
ハッシュ値
↓
格納場所
という流れです。
衝突が発生した場合には、
チェイン法
オープンアドレス法
などで解決します。
木・グラフ探索では、
DFS
→ スタック・再帰
BFS
→ キュー
という関係を押さえます。
さらに、
重みなしグラフの最短経路
→ BFS
非負の重み付きグラフの最短経路
→ ダイクストラ法
という違いも重要です。
41. まとめ
探索アルゴリズムは、
複数のデータの中から目的のデータを見つけるための手順
です。
単純に順番に探すなら、
線形探索
→ O(n)
整列済みデータから効率よく探すなら、
二分探索
→ O(log n)
ハッシュ表を利用するなら、
ハッシュ探索
→ 平均O(1)
という特徴があります。
木やグラフでは、
DFS
→ 深く探索
→ スタック・再帰
BFS
→ 広く探索
→ キュー
という探索方法があります。
この記事で覚えること
- 探索とは目的のデータを見つける処理
- 線形探索は先頭から順番に調べる
- 線形探索はO(n)
- 番兵法を使うと線形探索の終了判定を単純化できる
- 二分探索では探索範囲を半分ずつ減らす
- 二分探索には整列済みデータが必要
- 二分探索はO(log n)
- ハッシュ探索ではキーから格納場所を求める
- ハッシュ探索は平均O(1)
- 同じハッシュ値になることを衝突という
- 衝突はチェイン法やオープンアドレス法などで処理する
- 二分探索と二分探索木は別物
- 二分探索木は偏ると探索が最悪O(n)になる
- バランス木では木の高さを抑えて探索性能を保つ
- DFSは深い方向を優先して探索する
- DFSはスタックや再帰と相性がよい
- BFSは近いノードから探索する
- BFSはキューと相性がよい
- 重みなしグラフではBFSで最短経路を求められる
- 非負の重み付きグラフではダイクストラ法が利用できる
- 探索アルゴリズムはデータの状態やデータ構造に応じて使い分ける
🍯 はちみつメモ
探索は「どう探すか」だけでなく、「データがどう並んでいるか」が大事。バラバラなら線形探索、整列済みなら二分探索、キーから場所を計算できるならハッシュ探索。木やグラフならDFS・BFSの出番になる。