二分探索の最大探索回数An＝⌊log₂n⌋＋1の証明｜直感と数学的導出をわかりやすく解説

二分探索において「最大で何回比較すれば必ず解に到達できるのか」という問題は、アルゴリズムの本質を理解するうえで重要なテーマです。本記事では、探索回数の最大値Anが⌊log₂n⌋＋1になる理由について、直感的な理解と数学的証明の両面から解説します。

① 二分探索の基本構造

二分探索は、整列されたn個の要素を半分ずつに分割しながら目的の値を探すアルゴリズムです。

1回の操作ごとに探索範囲はおよそ1/2に減少します。

この「半分にする」という性質が対数的な振る舞いの根本です。

n個の要素を1個にまで絞り込むには、何回半分にできるかを考えます。

n → n/2 → n/4 → … → 1 となるまでの回数が探索回数です。

これは2の何乗でnを超えるか、という問題に帰着します。

k回の分割で1要素になるとすると、n / 2^k ≤ 1 が成立します。

これを変形すると 2^k ≥ n となり、k ≥ log₂n が得られます。

したがって最小の整数kは⌈log₂n⌉となりますが、探索回数の定義により⌊log₂n⌋＋1として表現されます。

二分探索では比較回数が「区間の分割回数＋最後の確認1回」を含みます。

そのため単純な⌈log₂n⌉ではなく、⌊log₂n⌋＋1の形で表す方が実装と一致します。

この違いは「何回目で確実に1要素に収束するか」という定義の違いです。

Anは最悪ケースにおける探索回数を表します。

すべての分割が最も不利に進んだ場合でも、この回数以内で必ず解に到達できます。

したがってAn＝⌊log₂n⌋＋1は上界としての保証値です。

二分探索の本質は「半分にする操作の繰り返し」であり、その回数は対数で表されます。

探索回数Anはlog₂nに基づき、実際の比較回数を正確に表すため⌊log₂n⌋＋1となります。

この関係を理解すると、二分探索の計算量O(log n)の意味もより明確になります。