アルゴリズム (全70問中57問目)

No.57

2分探索に関する記述のうち,適切なものはどれか。
  • 2分探索するデータ列は整列されている必要がある。
  • 2分探索は線形探索より常に速く探索できる。
  • 2分探索は探索をデータ列の先頭から開始する。
  • n個のデータの探索に要する比較回数は,nlog2nに比例する。
  • [この問題の出題歴]
  • 基本情報技術者 H26秋期 問6

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

2分探索法は、要素が昇順または降順に整列された集合に対して、探索範囲を1/2に狭めることを繰り返して目的のデータを探索するアルゴリズムです。
2分探索法では目的とする値が与えられると、まず探索範囲の中央に位置する値と目的値を比較します。そして目的値の方が小さければ中央から探索範囲の最後までを、目的値の方が大きければ探索範囲の最初から中央まで探索範囲から除外して、探索範囲を1/2にします。そして再度、新たな探索範囲の中央値と目的値を比較して探索範囲を半分にする、というように同じ操作を再帰的に繰り返します。
  • 正しい。2分探索を適用するにはデータが整列されていることが条件です。
  • 線形探索より少ない平均比較回数で目的のデータにたどりつけますが、データ列の先頭付近に目的のデータがあるケースでは線形探索のほうが探索が早くなります。
  • 探索範囲の中央に位置する値との比較から開始します。
  • 探索対象のデータ範囲がN個のとき、2分探索における平均比較回数は [log2N]です。([a]はaを超えない最大の整数を表します。)
© 2010-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop