探索アルゴリズムとは（全体像）
探索は、たくさんのデータから「目的のもの」を見つけ出す処理。見つけ方（アルゴリズム）にはいくつもあり、速さや前提条件が違う。
大きく2つの場面に分けて押さえる。
- 配列の探索 … 並んだデータの中から探す（線形探索・2分探索など）。
- グラフの探索 … 点と線のつながりをたどって探す（BFS・DFS）。
配列では、先頭から順に見る線形探索（O(n)）が一番単純。これを大幅に速くしたのが2分探索（O(log n)）だが、使うには条件がある——というのが第一のポイントだ。
詳しく：2分探索の前提とBFS・DFSだけ覚えれば戦える
ここが記事の心臓部。まずは配列の探索。
配列の探索
| 探索 | 速さ | 前提 |
|---|---|---|
| 線形探索 | O(n)（遅い） | なし（並んでいなくてOK） |
| 2分探索 | O(log n)（速い） | 並べ替え済み（ソート済み）が必須 |
2分探索は、まん中の要素と比べて「探すものは右半分か左半分か」を判断し、毎回範囲を半分に絞る。とても速い（O(log n)）が、並べ替え済みでないと使えない——ここが最頻出のひっかけだ。
次に、グラフの探索BFSとDFS。
BFSとDFSの違い
| BFS（幅優先） | DFS（深さ優先） | |
|---|---|---|
| 進み方 | 近い順に広げる | 奥まで進んで戻る |
| 使う構造 | キュー | スタック（や再帰） |
| 最短経路 | 保証する | 保証しない |
BFS（幅優先探索）は、出発点に近いところから順に広げていく。だから「最も少ないステップでたどり着く道（最短経路）」を保証する（キューを使う）。DFS（深さ優先探索）は、行けるところまで奥へ進んでから戻る（スタックや再帰を使う）。
ここが頻出ポイントで、最短経路を保証するのはBFS。DFSは奥へ進むため、必ずしも最短にならない。「最短ならBFS」と覚える。つまり、目的が最短経路かどうかでBFSとDFSを選び分ける、というわけだね。
なお、ハッシュ表を使えば平均O(1)でほぼ一発で探せる（ハッシュ探索）。
わかりやすく言い換えると
要するに、探索は「見つけ方の選び方」だ。
①2分探索 … 辞書引き。まん中を開いて「もっと前か後か」を判断し、半分に絞る。ただし五十音順に並んでいるから使える（バラバラの紙束では無理）。
②BFS（幅優先） … 池に石を落として広がる波紋のように、近い順に探す。だから最短の道が見つかる。
③DFS（深さ優先） … 迷路で「まっすぐ進めるところまで進んで、行き止まりで戻る」やり方。
「最短経路がほしいならBFS、奥まで一気に調べたいならDFS」と、目的で選ぶ、というわけだね。
試験のツボ
🔴 一番出る：2分探索の前提
①2分探索は範囲を半分ずつ絞ってO(log n)と速い
②ただし並べ替え済み（ソート済み）でないと使えない
🔴 次に出る：BFSとDFSの違い
①BFS＝幅優先・キュー・最短経路を保証
②DFS＝深さ優先・スタック（や再帰）・奥まで進む
🟡 押さえると安定：探索の速さ
①線形探索＝O(n)（前提なし）
②ハッシュ探索＝平均O(1)（ハッシュ表を使う）
よくある間違い
①「2分探索は並べ替えていないデータでも使える」→ ✗ 2分探索は並べ替え済み（ソート済み）が前提。並んでいないなら使えない。
②「最短経路を保証するのは深さ優先探索（DFS）である」→ ✗ 最短経路を保証するのはBFS（幅優先）。DFSは奥へ進むので保証しない。
③「BFSはスタック、DFSはキューを使う」→ ✗ 逆。BFSはキュー、DFSはスタック（や再帰）を使う。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（2分探索の前提）
2分探索に関する次の記述のうち、正しいものはどれか。
- 2分探索は並べ替えていないデータでも、範囲を半分ずつ絞って速く探せる
- 2分探索は並べ替え済みのデータで、半分ずつ絞ってO(log n)で探す
- 2分探索は先頭から1つずつ順に確認する、O(n)で遅い探索のことである
- 2分探索はデータの個数によらず、つねにO(1)で一発で探せるものである
解答は 2 だよ。
2分探索は並べ替え済みのデータで使え、まん中と比べて範囲を半分ずつ絞ってO(log n)で探すんだ。辞書引きのイメージだね。
選択肢1は「並べ替えていなくても使える」が誤り（ソート済みが前提）。選択肢3は線形探索の説明。選択肢4は「O(1)」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 並べ替え済みが前提 |
| 2 | ✓ | ソート済み・半分ずつ絞ってO(log n) |
| 3 | ✗ | それは線形探索 |
| 4 | ✗ | O(log n)であってO(1)ではない |
オリジナル問題2（最短経路）
グラフ探索で最短経路（最も少ないステップの道）を保証する探索として、正しいものはどれか。
- 深さ優先探索（DFS）は近い順に広げるため、最短経路を必ず保証している
- 線形探索が最短経路を保証し、BFSやDFSは経路の長さとは無関係である
- DFSもBFSも最短経路を保証しないので、最短はどちらでも求められない
- 幅優先探索（BFS）は出発点から近い順に広げるため、最短経路を保証する
解答は 4 だよ。
幅優先探索（BFS）は出発点に近い順に広げるから、最短経路を保証するんだ。池の波紋のように、近いところから探していくイメージだね。
選択肢1はDFSを「最短保証」とする誤り（保証するのはBFS）。選択肢2は線形探索を最短とする誤り。選択肢3は「どちらも保証しない」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 最短を保証するのはBFS |
| 2 | ✗ | 最短保証はBFS |
| 3 | ✗ | BFSは最短を保証する |
| 4 | ✓ | BFSは近い順に広げ最短を保証 |
オリジナル問題3（BFSとDFSの構造）
BFSとDFSが使うデータ構造に関する次の記述のうち、正しいものはどれか。
- BFSもDFSもスタックを使うので、進み方にとくに違いはないものである
- BFSはスタックを使って近い順に、DFSはキューを使って奥へ進むものだ
- BFSはキューを使って近い順に広げ、DFSはスタックを使って奥へ進む
- BFSもDFSもデータ構造を使わず、ランダムに探索を進めるものである
解答は 3 だよ。
BFSはキューを使って近い順に広げ、DFSはスタック（や再帰）を使って奥へ進むんだ。「近い順のBFSはキュー、奥へ進むDFSはスタック」とセットで覚えてね。
選択肢1は「ともにスタック」が誤り。選択肢2はBFSとDFSの構造が逆。選択肢4は「使わない」が誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | BFSはキューを使う |
| 2 | ✗ | BFSとDFSの構造が逆 |
| 3 | ✓ | BFS＝キュー・DFS＝スタック |
| 4 | ✗ | それぞれデータ構造を使う |
まとめ
押さえどころ
- 🔴 2分探索 ＝ 半分ずつ絞ってO(log n)と速い。ただし並べ替え済み（ソート済み）が前提。
- 🔴 BFSとDFS ＝ BFSは幅優先・キュー・最短経路を保証、DFSは深さ優先・スタック（や再帰）。
- 🟡 探索の速さ ＝ 線形探索O(n)（前提なし）、ハッシュ探索は平均O(1)。
次に学ぶ
- グラフ理論（最小全域木・最短経路） ── BFS・DFSが活躍する「点と線」の世界。最短経路の考え方が深まる。
- ハッシュ表（衝突対応） ── 平均O(1)で探せるハッシュ探索のしくみ。探索を一気に速くする方法が分かる。
執筆: SikakuQuest編集部