は、入力サイズ の対数に比例する計算量で、対数時間と呼ばれます。データが 2 倍になっても処理量は +1 程度しか増えないため、大規模データでも非常に高速なのが最大の特徴です。
| データ数 N | おおよその処理量（log₂ N） |
|---|---|
| 1,000 | 約 10 |
| 1,000,000 | 約 20 |
| 1,000,000,000 | 約 30 |
2 分探索（2 分探索）・平衡 2 分木の操作・ヒープの挿入や削除などが代表例です。10 億件あっても約 30 回の比較で済むイメージで、 とは桁違いに速くなります。
たとえば 1,000 件のデータから 2 分探索で 1 件を探すと、比較はおよそ 10 回で済みます。件数を 100 万件へ 1,000 倍に増やしても約 20 回にしかならず、増え方が非常にゆるやかです。
試験では は「範囲を半分ずつ絞る」処理に現れること、2 分探索の計算量であることが問われます。
