多くのデータの中から目的の要素を探し出すこと。代表は3つ。
先頭から順に1つずつ照合。未整列でもOKだが遅い。
整列済みの配列限定。中央と比べて探索範囲を毎回半分に絞る。
キーをハッシュ関数で計算し、格納場所を直接求める。最速。
計算量は「データの個数 n が増えたとき、処理の手間（比較回数など）がどれだけ増えるか」の目安。
細かい定数や小さい項を無視して「n が大きいとき一番効く部分」だけで表したものがオーダで、O( ) と書く。
| オーダ | 増え方 | n を10倍にすると手間は |
|---|---|---|
| O(1) | n に関係なく一定 | 変わらない |
| O(log n) | とても緩やかに増える | ほんの少し（＋数回） |
| O(n) | n に比例 | 約10倍 |
この章の3つの探索法：
| 探索法 | 平均比較回数 | オーダ | なぜそのオーダか |
|---|---|---|---|
| 線形探索 | n/2 | O(n) | 先頭から順に見るので、最悪 n 個ぜんぶ確認 |
| 2分探索 | 約 log₂n | O(log n) | 1回の比較で範囲が半分になるので、半分にできる回数だけで済む |
| ハッシュ | 1 | O(1) | 計算で格納場所を直接求めるので、基本1回で届く |
Q1（H16春 問15）★線形探索の流れ図
配列 A の1〜N番目に整数が格納（N>1）。X と同じ値が何番目かを調べる、次の流れ図の実行結果として正しいものはどれか。
正解：ウ
変数 k は「今何番目を見ているか」。値が一致するとループを抜けるので、
▼速解法：線形探索は前から順。複数一致なら最初の位置で止まる。
Q2 ★2分探索の最大探索回数
2分探索で、整列されているデータの個数が4倍になると、最大探索回数はどう変わるか。
正解：イ（2回増える）
2分探索は1回の比較でデータが半分になる。
▼速解法：データが2倍 → 1回増える を基準に。4倍=2²倍だから2回、8倍なら3回。（最大探索回数 ≒ log₂n の関係）
▼ 解説つきの類題を探す：過去問道場・分野別「アルゴリズム」
Q3（H27春 問6）★2分探索の計算量オーダ
整列済みの n 個のデータから、2分探索で要素を探すときの計算量のオーダはどれか。
正解：ア（O(log n)）
1回の比較で範囲が半分になる。n を 1 になるまで半分にする回数が比較回数 → n = 2ˣ より x = log₂n。よって O(log n)。
Q4 ★2分探索の最大比較回数
1,000,000 件の整列済みデータを2分探索するとき、最大比較回数はおよそ何回か。
正解：イ（約 20 回）
2¹⁰ ≒ 1,000、2²⁰ ≒ 1,000,000。つまり log₂(1,000,000) ≒ 20。
100万件でもたった20回。線形探索なら最大100万回なので、2分探索の速さが分かる。
▼ 解説つきの類題を探す：過去問道場・分野別「アルゴリズム」
Q5 ★ハッシュのシノニム
ハッシュ関数を h(x) = x mod 10（10 で割った余り）とする。データ 12, 25, 32, 45 を格納するとき、同じ格納場所（シノニム）になる組はどれか。
正解：エ
シノニムの組は (12, 32) と (25, 45)。衝突したデータの逃がし方（オープンアドレス法／チェイン法）で対処する。
Q6 ★2分探索のトレース
整列済み配列（添字 1〜7）から 21 を2分探索する。中央要素として比較する値を、比較する順に並べたものはどれか。
正解：ア（11 → 17 → 21）
| Low | High | mid（添字） | A[mid] | 21 との比較 |
|---|---|---|---|---|
| 1 | 7 | 4 | 11 | 21 > 11 → 右へ（Low=5） |
| 5 | 7 | 6 | 17 | 21 > 17 → 右へ（Low=7） |
| 7 | 7 | 7 | 21 | 一致（発見） |
mid ＝ (Low+High)÷2 の整数部。比較したのは 11 → 17 → 21 の3回。
▼速解法：毎回残り範囲の真ん中と比べ、大小で左半分／右半分に絞る。1回で範囲が半分になる。
▼ 解説つきの類題を探す：過去問道場・分野別「アルゴリズム」