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

2分探索は、要素が昇順または降順に整列された集合に対して、探索範囲の中央に位置する値と探索する値を比較し、探索する値の方が小さければ目的の値は範囲の先頭から中央までに、探索する値の方が大きければ目的の値は範囲の中央から最後までに存在すると判断して、次回は探索範囲を1／2に狭めて探索することを再帰的に繰返すことで目的のデータを探索するアルゴリズムです。

2分探索では、1回の探索・比較を行うごとに探索範囲を1／2に狭めていくため、探索・比較を2回行うと探索範囲は1／4に減少します。
したがってデータの個数が4倍になった場合の最大探索回数は、元の回数より2回だけ増えることになります。