二分探索の前提条件
二分探索は、中央の要素と目的値を比較し、目的値があり得ない半分の範囲を捨てながら探索する手法です。この判断が正しく成り立つには、データが昇順または降順にソート済みである必要があります。したがって正解は「データがソート済みであること」です。 (選択肢1が正しい)
正解の理由
二分探索は、中央の要素と目的値を比較し、目的値があり得ない半分の範囲を捨てながら探索する手法です。この判断が正しく成り立つには、データが昇順または降順にソート済みである必要があります。したがって正解は「データがソート済みであること」です。
仕組み・頻出ポイント
- 各ステップで候補範囲を約半分にできるため、最悪計算量は (O(log n)) になります。
- ソート済みでなければ、中央より小さい・大きいという比較から左右どちらを捨てるべきか判断できません。
- 探索前にソートする場合は、ソートの計算量も含めて全体のコストを考える必要があります。
G検定で覚えるべきこと
「高速な探索手法」という印象だけで選ぶと、未整列データにも使えると誤解しがちです。実務では、同じデータに何度も検索をかけるなら事前ソートや索引構造が有効ですが、一回だけの探索なら線形探索の方が総コストで有利な場合もあります。
他の選択肢の評価
- 選択肢1: 正解です。整列順序があるからこそ探索範囲を半分にできます。
- 選択肢2: 整数である必要はなく、大小比較できるデータであれば文字列や日付でも考えられます。
- 選択肢3: データ数が偶数か奇数かは本質ではありません。中央の取り方を決めれば処理できます。
- 選択肢4: 重複値があっても探索自体は可能です。ただし最初の位置や範囲を求める場合は追加処理が必要です。
実務での見方
実務では、二分探索そのものよりも「探索しやすい形にデータを整える」発想が重要です。検索が繰り返されるなら、最初にソートするコストを払っても全体では高速になることがあります。逆に、データ更新が頻繁な場合は、整列状態の維持コストも考える必要があります。
確認観点
確認観点としては、ソート済みであること、大小比較が定義できること、検索対象の範囲を正しく更新できることです。これらが崩れると、(O(log n)) の速さ以前に正しい結果を保証できません。
結論として、この問題では「用語の定義」だけでなく、どの前提で使えるのか、どの誤解を避けるべきか、実務では何を確認するのかまで結びつけて理解することが重要です。