分野別過去問題テクノロジ系　アルゴリズム No.27

アルゴリズム(全80問中27問目)

整列されたn個のデータの中から，求める要素を2分探索法で探索する。この処理の計算量のオーダーを表す式はどれか。

出典：平成27年春期　問 6

正解　ア問題へ

分野：テクノロジ系
中分類：アルゴリズムとプログラミング
小分類：アルゴリズム

解説

2分探索法は、要素が昇順または降順に整列された集合に対して、探索範囲を1／2に狭めて探索することを再帰的に繰り返して目的のデータを探索するアルゴリズムです。

2分探索法では、データの個数 n と計算量 x の関係は下表のようになっています。

この関係を立式すると

　n＝2^x

2を底として対数(log)をとると、

　log₂n＝x

つまり計算量のオーダーは O(log n) になります。