ITの基礎知識｜ITパスポート・基本情報

基本情報技術者 平成21年春 問7

2017.10.04

昇順に整列されたｎ個のデータが配列に格納されている。探索したい値を二分探索法で探索するときの、およその比較回数を求める式はどれか。

  • ア：　　log2n
  • イ：　　( log2n ＋1 ) ／ 2
  • ウ：　　n
  • エ：　　n2

 

Show answer

基本情報過去問 , アルゴリズム

正解：　ア

解説：

二分探索法は、対象データが探索範囲の前方にあるか、後方にあるかで、探索範囲を半分にすることを繰り返すので、二分探索法の凡その比較回数は、対象データを2等分できる回数であり、「 log2n」で求められる。