アルゴリズムとは
アルゴリズムとは、問題を解くための手順であり、整列の有無など前提によって適した方法が変わります。
大量の番号から目的の番号を探すとき、毎回すべてを読む必要があるでしょうか。整列済みなら、中央との比較で候補を半分にできます。
基本の仕組み
1、3、5、7、9、11、13から11を探すと、中央7より大きいので右半分へ進み、9、11、13の中央11で一致します。
二分探索は整列を前提とし、比較のたびに下限または上限を更新します。候補を約半分にするため、探索の比較回数は要素数nに対しておおむねlog₂nの規模です。最大比較回数は⌊log₂n⌋＋1回（⌊ ⌋は小数点以下切捨て）で、16個なら5回です。
未整列の配列では、中央より大きい値が左にもあるため半分を捨てられません。添字の更新を誤ると同じ範囲を繰り返して終了しない場合があります。
探索方法の前提
線形探索は未整列でも使えます。n個から探すと比較回数は最悪n回、見つかる場合の平均は(n＋1)/2回で、計算量はO(n)です。二分探索は整列済みを前提にO(log n)です。二分探索では、下限・上限の更新後も候補範囲が必ず縮むかを確かめます。
ハッシュ探索は、キーから計算した位置（ハッシュ値）を直接調べます。異なるキーが同じ位置になる衝突が少なければ平均O(1)ですが、衝突が多いと比較回数が増えます。
| 探索 | 必要な前提 | 比較回数の目安 |
|---|---|---|
| 線形 | 整列不要 | 平均(n＋1)/2回、最悪n回 |
| 二分 | 整列済み | 最大⌊log₂n⌋＋1回 |
| ハッシュ | キーの変換と衝突処理 | 衝突がなければ1回 |
試験に出る
- 二分探索は整列済みが前提という条件。
- 比較のたびに下限・上限を更新し、候補が約半分になること。
- 探索の比較回数が要素数nに対しておおむねlog₂n、最大は⌊log₂n⌋＋1回であること。線形探索の平均(n＋1)/2回との比較。
- 未整列では中央で半分を捨てられないこと。
- 添字更新を誤ると終了しない場合があること。
重要な言葉
- 二分探索
- 整列済みのデータで中央と比較し、候補を半分に絞る探索。
- 計算量
- 処理に必要な手間を要素数との関係で表した量。
- 線形探索
- 先頭から順に比較して目的の値を探す方法。
確認問題
確かめよう候補が16個なら、半分に4回絞ると何個？
1個。16→8→4→2→1です。
二分探索は、データが未整列でも使える。
候補が16個のとき、半分に絞る操作を4回行うと1個になる。
二分探索が前提とする条件は？
候補16個を半分に絞る操作を繰り返すと、1個になるまで何回？
大量の番号から目的の番号を探すとき、毎回すべてを読む必要があるでしょうか。なら、中央との比較で候補をにできます。
1、3、5、7、9、11、13から11を探すと、より大きいのでへ進み、9、11、13の中央11で一致します。
は整列を前提とし、比較のたびに下限または上限を更新します。候補を約半分にするため、探索の比較回数は要素数nに対しておおむねの規模です。最大比較回数は⌊log₂n⌋＋1回（⌊ ⌋は小数点以下切捨て）で、16個なら5回です。
の配列では、中央より大きい値が左にもあるため半分を捨てられません。の更新を誤ると同じ範囲を繰り返して終了しない場合があります。
出典・参考資料
試験の公式案内と、この記事の参考にした学習資料です。
編集：Pinternet Works · 更新日：
教材の編集方針・訂正について