問題

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

ア　log2 n
イ　(log2 n＋1)／2
ウ　n
エ　n2

テクノロジ系>基礎理論>アルゴリズムとプログラミング>アルゴリズム

解説と解答

　2分探索法は，整列済みの配列から効率よくデータを探索するための方法です。

　具体的には，配列の中央のデータと探したいデータを比較し，探したいデータ値の要素が配列の前半にあるか後半にあるか判断し，検索対象範囲を半分に絞り込みます。そして，絞り込んだ検索対象範囲の中央の値と探したいデータを比較し，再び探索範囲を半分に絞り込みます。これを繰り返して，目的のデータを探索します。

　要素数がn個の場合に2分探索法を使った場合の比較回数は，次の式で求めることができます。

平均比較回数：(log2n)回
最大比較回数：(log2n)＋1回

　よって正解は，選択肢アです。

佐塚 彰夫（さづか あきお）
アイティ・アシスト 代表取締役
ITに関するコンサルティングや教育を実施するアイティ・アシストの代表。新人研修やプロジェクトマネージャ育成研修をはじめ，基本情報技術者試験，応用情報技術者試験，プロジェクトマネージャ試験などの試験対策研修の実績も豊富。著書に「短期完全マスター 基本情報技術者 2009年版」などがある。