探索アルゴリズムを理解する
探索はデータ集合から目的の値を見つける処理である。線形探索は先頭から順に調べ、二分探索は整列済みデータの探索範囲を半分ずつ絞る。
この単元で学ぶこと
- 線形探索の意味と役割を説明できる
- 二分探索の意味と役割を説明できる
- low/highの意味と役割を説明できる
- 線形探索と二分探索の前提・更新規則・計算量を説明できる
本文解説
線形探索は未整列でも使えるが最悪O(n)。二分探索は整列済みでランダムアクセスしやすいデータに向き、最悪O(log n)。前提条件を無視すると誤った探索になる。
線形探索 要素を先頭から順番に比較する探索。 未整列データでも使える。
二分探索 中央要素と比較して探索範囲を半分へ絞る探索。 整列済みであることが前提。
low/high 二分探索で現在の探索範囲の両端を表す変数。 比較結果でどちらかをmidの外側へ更新する。
mid 探索範囲中央の添字。 整数化方法は設問定義に従う。
探索失敗 探索範囲が空になるまで見つからない状態。 二分探索ではlow>highなどで判定する。
二分探索ではまず「整列済みか」を確認し、low/high/midを表にする。
[2,5,8,12,20]で12を探すとmid=2の8より大きいので右半分へ進む。
図解
重要ポイント
- 線形探索: 要素を先頭から順番に比較する探索。
- 二分探索: 中央要素と比較して探索範囲を半分へ絞る探索。
- low/high: 二分探索で現在の探索範囲の両端を表す変数。
- mid: 探索範囲中央の添字。
- 二分探索は高速だから常に使えるのではなく、整列済みという前提がある。
間違えやすい点
- 未整列配列へ二分探索を適用しない。
- mid比較後にmid自身を再び探索範囲へ残さない。
- low>highの終了条件を見落とさない。
用語解説
- 線形探索
- 要素を先頭から順番に比較する探索。
- 二分探索
- 中央要素と比較して探索範囲を半分へ絞る探索。
- low/high
- 二分探索で現在の探索範囲の両端を表す変数。
- mid
- 探索範囲中央の添字。
- 探索失敗
- 探索範囲が空になるまで見つからない状態。
関連教材
参考資料
教材データに登録された参考リンクです。リンク先の内容や更新日は提供元でご確認ください。
確認問題の出題・採点や学習履歴の保存にはログインが必要です。