Let’s 競技プログラミング! E8さんが教えるアルゴリズム発想のキホン(4) 二分探索法とは？

二分探索法は、値の検索を効率的に行うアルゴリズムの一つです。いくつかの要素の中に「ある要素」が存在するかどうかを判定する際、一つずつ調べていくのが最も自然な方法ですが、それでは時間がかかってしまいます。そこで、候補の数を半分に減らし続けることで、効率的に検索を行おうという考え方が二分探索法です。今回は、受験の合格発表を例にして、このアルゴリズムを解説します。

合格発表の問題

次の掲示板には合格者 63 名の受験番号が記されています。そこに、自分の受験番号（仮に、2525 番とする）が存在するかどうかを調べてみましょう。どのようにすれば効率的に見つけられるでしょうか。

方法 1 ：一つずつ探していく

まず、「1008 番は自分の受験番号か？」「1025 番は自分の受験番号か？」「1066 番は自分の受験番号か？」といったように、前から順番に一つずつ調べる方法が考えられます。しかしこの方法を使うと、最大 63 回の比較を行う必要があり、非効率的です。実際の合格発表では人数がさらに多い場合もあり、時間がかかってしまいます。

方法 2 ：まず何列目かを調べる

そこで、自分の受験番号が何列目にあるかを調べてから、その列に絞って番号を探す方法が考えられます。例えば受験番号 2525 を探す手順は次のようになります。

手順 1 ：一番上の行を確認し、自分の番号が何列目にあるかを調べる
手順 2 ：自分の受験番号は 2377 以上 2601 未満なので、 7 列目にあることが分かる
手順 3 ：7 列目のどこに自分の番号があるかを一つずつ確認する

この場合、合計 16 回（手順 1 と 3 それぞれ 8 回ずつ）の比較をする必要があります。方法 1 よりは効率的になりましたが、さらに効率良く自分の番号を探す方法はないでしょうか。

方法 3 ：二分探索法を使う

最初の時点では、「自分の受験番号の位置としてあり得る範囲」は 1 番目から 63 番目までの間となりますが、うまく発想すると 1 回の比較で範囲を半分に絞ることができます。まず、自分の受験番号を中央（32 番目）の合格番号 1845 と比較することを考えましょう。このとき、次のことが分かります。

自分の受験番号 < 1845 の場合：左半分（1 ～ 31 番目）に番号があること
自分の受験番号 = 1845 の場合：合格したこと
自分の受験番号 > 1845 の場合：右半分（33 ～ 63 番目）に番号があること

いずれの場合も、範囲を半分以下に絞ることができます。 2 回目以降も、「今考えられる範囲」の中央の合格番号と自分の受験番号を比較することで、範囲を半減させることが可能です。

これを繰り返すと、範囲内にある番号の数が 63 個→ 31 個→ 15 個→ 7 個→ 3 個→ 1 個と減っていき、必ず 6 回以内で自分の番号を見つけることができます。下図は、この手順に沿って受験番号 2525 を見つける過程を表したものです。このようなアルゴリズムは二分探索法と呼ばれています。

問題を一般化してみよう

次に、合格発表の問題を一般化した、以下の問題を考えてみましょう。

小さい順に並べられているN個の整数A₀, A₁, …, A_N-1が与えられます。この中に整数 x が存在するかどうかを判定してください。入力・出力を除いて計算量O(log N)であることが望ましいです。

この問題も、探索範囲を半減していく方針で解くことができます。厳密にアルゴリズムを記すと、次のようになります。

探索範囲の左端を L、右端を R とする。最初は L=0, R= N-1 である
探索範囲がなくなる（L>R になる）まで、次の操作を繰り返す
1. 探索範囲の中央の位置を M とする
2. x < AM であれば x は中央より左側にあることが分かるので、R = M - 1 とする
3. x = AM であれば x は存在するので、Yes と出力する
4. x > A_M であれば x は中央より右側にあることが分かるので、L = M + 1 とする
探索範囲がなくなっても見つからなかった場合、No と出力する

例えば、A = [10, 12, 23, 35, 68, 90, 97]、x = 68 の場合、アルゴリズムは下図のように動作します。

このアルゴリズムを Python で実装すると、次のようになります。

import sys

# 入力
N = int(input())
X = int(input())
A = list(map(int, input().split()))

# 二分探索
l = 0
r = N - 1
while l <= r:
    m = (l + r) // 2
    if A[m] < X:
        l = m + 1
    elif A[m] == X:
        print("Yes")
        sys.exit()
    else:
        r = m - 1

# 最後まで見つからなかった場合
print("No")

二分探索法の計算量

最後に、二分探索法の計算量を考えてみましょう。1回の比較で探索範囲が半減するので、与えられた整数の個数をNとすると、探索範囲の大きさは次表のように減っていきます。

比較回数	1 回目	2 回目	3 回目	4 回目	...	T 回目
探索範囲	N	N/2 以下	N/4 以下	N/8 以下	...	N/2^T-1 以下

探索範囲は1回未満になり得ないので、N/2^T-1 ≥ 1、すなわちT ≤ log₂ N+1 を満たす必要があります^※。したがって、比較回数はせいぜいlog₂ N+1 回であり、計算量はO(log N)となります。

今回は、合格発表の掲示を例にして、二分探索法を解説しました。次回はこれを応用した手法である「答えを二分探索するテクニック」を紹介しますので、ご期待ください。

※ N/2^T-1≥ 1のとき、2^T-1 ≤ Nを満たします。そこで対数関数の定義より、2^x = Nのときx = log₂ Nが成り立ちます。このことから、T-1 ≤ log₂ Nが分かります。

二分探索法とは？