基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

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

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

　n＝2^x

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

　log₂n＝x

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