14 いろいろな探索アルゴリズム
1. この章の狙い
前章（12章）で線形探索をじっくり学びました。
本章では「線形探索以外にも、こんな探し方があるよ」というカタログをざっくり見ていきます。
今回のスタンス：
各アルゴリズムを完璧に理解する必要はありません。
「○○探索はこんな感じ」というイメージと、使いどころの違いがわかればOK。
細かいコードは後の練習問題で身につきます。
2. 二分探索（binary search）
キーアイディア
ソート済みの配列に対して、真ん中の値と比べて、左半分か右半分に絞る。
これを繰り返すと、毎回範囲が半分になり、目的の値に高速に到達します。
計算量 O(log n)：
比較するごとに範囲が半分になる。
100万件の配列でも約 20回 の比較で答えが出る（線形探索なら最悪100万回）。
条件：配列が必ずソート済みであること。
ソートされていない配列には使えない。
3. ハッシュ探索（hash search）
キーアイディア
キーをハッシュ関数で添字に変換し、配列のその位置を直接見る。
比較を繰り返さず、計算1発で場所が分かる。
計算量 平均 O(1)：データ数によらず一発で見つかる。
ただし「衝突」（別キーが同じ添字になる）の処理が必要。詳しくは18章で。
4. 二分探索木による探索
キーアイディア
19章で学ぶ二分探索木（左の子＜親＜右の子）を使うと、
根から「小さければ左、大きければ右」と進むだけで目的の値に到達できます。
計算量 平均 O(log n)：
二分探索と同じく半分ずつ絞れる。19章でしっかり扱う。
5. グラフ探索（DFS / BFS）
キーアイディア
友達のつながりや道路網のようなグラフ構造から、目的の頂点を探す。
「深く潜る」か「近い順に広げる」かで2タイプあります。
| 名前 | 進み方 | 使うデータ構造 | 得意 |
|---|
| 深さ優先探索（DFS） | 1本の道を行けるとこまで進む | スタック・再帰 | 到達可能性、迷路 |
| 幅優先探索（BFS） | 近い頂点から順に広げる | キュー | 最短経路（無向） |
グラフと、これらの探索アルゴリズムについては、後の章で詳しく扱います。
ここでは「2種類あって、性質が違う」を覚えておけばOK。
6. 一目で比較
| 探索手法 | 前提 | 速さ | 主な用途 |
|---|
| 線形探索 | なし | 遅い（O(n)） | 小さい配列、ソートできないデータ |
| 二分探索 | 配列がソート済み | 速い（O(log n)） | 大きいソート済み配列 |
| ハッシュ探索 | ハッシュ関数の準備 | とても速い（平均 O(1)） | キーで値を引きたい場合 |
| 二分探索木 | 木が構築済み | 速い（平均 O(log n)） | 順序付きで挿入・検索したい |
| DFS / BFS | グラフ・木構造 | O(頂点数+辺数) | つながりをたどる |
覚え方：
・並んでない → 線形探索
・並んでいる → 二分探索
・キー → 値 → ハッシュ
・つながりがある → グラフ探索
7. 理解度チェック問題
問題14-1
「ソートされた配列から目的の値を探す」場合、最も効率が良いのはどれか。
解説を表示
正解：イ
ソート済みなら毎回半分に絞れる二分探索（O(log n)）。
ウ・エ（ランダム・逆順）はそもそも線形探索以下で論外。
問題14-2
二分探索を使うために必須の条件はどれか。
解説を表示
正解：ウ
「半分に絞る」判断ができるのは、左右の大小関係が決まっているから。
そのためソート済みである必要がある。
ア・イ・エはどれも二分探索とは無関係。
問題14-3
「キーから値を素早く引きたい（例：学生IDから学生名）」のに最適な探索はどれか。
解説を表示
正解：エ
ハッシュ探索は平均 O(1) でキーから値を引ける。辞書・データベースのインデックスにも使われる。
ウ（BFS）はグラフ探索なので用途が違う、明らかに不適。
問題14-4
n = 1,000,000 のソート済み配列から二分探索で値を探す。最悪でも比較はおよそ何回か。
解説を表示
正解：ア
log₂(1,000,000) ≒ 20 回。
エ（100万回）は線形探索の回数で、二分探索を使う意味がない。