探索アルゴリズムと計算量

まず全体像：探索の3兄弟

探索の方法は、試験ではほぼ線形探索・2分探索・ハッシュ探索の3つに絞られます。違いは「データがどう並んでいる必要があるか（前提）」と「データ量 n が増えたとき、手間がどう増えるか（計算量）」の2点です。まずこの表を丸ごと覚えてください。

計算量とは「データ数 n に対して処理の手間がどう増えるか」を表すもので、オーダはその増え方の大まかな形（n に比例、log₂n に比例など）を指します。定数倍は無視して、形だけで比べます。

線形探索：流れ図は「どこで止まるか」を読む

線形探索は、配列の先頭（k=1）から順に「目的の値 X と等しいか」を比べ、等しければそこで終了します。見つからなければ k を 1 増やし、k が N を超えたら終了します。

流れ図の問題では、終了したときの k の値だけを押さえれば解けます。

比較回数を減らすコツ：線形探索は前から調べるので、よく出るものを前に置くほど平均の比較回数が減ります。処理区分の判定なら、出現比率が大きい区分から先に判定するのが正解です。

2分探索：前提は「整列済み」、中央は (x+y)/2

2分探索は、辞書で単語を引くときに真ん中あたりを開き、「目的の語はこのページより前か後か」で半分を捨てる動きと同じです。辞書が五十音順に並んでいるから前後を判断できるのであって、バラバラに並んだデータには使えません。これが最頻出の「前提条件」の論点です。

流れ図の決まり文句（探索範囲の下端を x（lo）、上端を y（hi）とする）：

• 中央の添字（配列の何番目かを表す番号）：(x+y)/2（小数点以下切捨て）
• 中央の値 < 探す値 → 目的は右半分 → 下端を m+1 にする
• 中央の値 > 探す値 → 目的は左半分 → 上端を m−1 にする
• 下端 > 上端 になったら範囲が空 → 見つからない

±1 するのは、今調べた m 自体はもう候補ではないからです。

flowchart TD
  A["x←1, y←n"] --> B{"x ≦ y ?"}
  B -- "No" --> Z["見つからない"]
  B -- "Yes" --> C["m←(x+y)/2"]
  C --> D{"A(m) と k を比較"}
  D -- "等しい" --> E["見つかった"]
  D -- "k が小さい" --> F["y←m−1（左半分へ）"]
  D -- "k が大きい" --> G["x←m+1（右半分へ）"]
  F --> B
  G --> B

探索表の並び方で手法を選ぶ問題も同じ考え方です。コード順に並んだ表 → 2分探索、使用頻度順に並んだ表（整列していない）→ 線形探索、コードから一意に場所が決まる表 → ハッシュ表探索、と対応させます。

計算量：log₂n を体で覚える

2分探索は1回比べるごとに候補が半分になります。n 件が 1 件になるまでに半分にする回数は、2 を何乗すると n になるか、つまり log₂n 回です。1,024 件なら 2¹⁰=1,024 なので約 10 回、約100万件でも約 20 回で済みます。

注意点として、2分探索は「1件を探す」処理なので log₂n、n log₂n は「全件を整列する」処理のオーダです。選択肢で並ぶので取り違えないでください。また、2分探索が線形探索より「常に」速いわけではありません（目的が先頭にあれば線形探索は1回で終わります）。

ブロック分割探索：2段階の線形探索

整列済みの n 件を m 件ずつのブロックに分け、まず各ブロックの最後尾だけを線形探索して「どのブロックにあるか」を決め、次にそのブロック内を線形探索します。線形探索の平均比較回数は「候補数の約半分」なので、ブロック選び (n/m)/2 回＋ブロック内 m/2 回で、平均 m/2 + n/(2m) になります。

比例計算：「何乗に比例」をそのまま使う

「計算時間が n³ に比例する」と言われたら、n が 10 倍になると時間は 10³=1,000 倍です。そのうえで、演算速度が 4 倍のコンピュータなら時間は 1/4 になります。データ量の倍率を指数どおりに乗じる → 速度の倍率で割る、の2段階で解きます。