配列の二分探索

問題

小さい順に並べられている要素数 $ N $ の配列 $ A = [A_1, A_2, …, A_N] $ があります。

要素 $ X $ は配列 $ A $ の何番目に存在するかを求めて下さい。

この問題は全探索でも解くことができますが、今回は二分探索を使って実装して下さい。

[制約]
🔹$ 1 \leqq N \leqq 100000 $
🔹$ 1 \leqq A_1 < A_2 < … < A_N \leqq 10^9 $
🔹探す整数 $ X $ は $ A_1,A_2,…,A_N $ のいずれかである

解き方・ソースコード

二分探索では、探索範囲の左側を $ L $ 番目、右端を $ R $ 番目とするとき、次のような処理によって探索範囲を半分に絞っていきます。

🔹$ M=(L+R)/2 $ とする（割り切れない場合は切り捨てる）
🔹$ X < A_M $ の場合：探索範囲を左半分にする（$ R $ の値を $ M - 1 $ にする）
🔹$ X = A_M $ の場合：答えは $ M $ である
🔹$ X > A_M $ の場合：探索範囲を右半分にする（$ L $ の値を $ M + 1 $ にする）

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#--------- 入力例１ ---------
N = 15      # 要素数
X = 47      # 探す要素
A = [8, 13, 17, 19, 24, 27, 33, 37, 41, 43, 47, 53, 59, 61, 68]
#--------- 入力例２ ---------
# N = 10      # 要素数
# X = 80      # 探す要素
# A = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
#----------------------------
# 整数 x が何番目に存在するかを返す関数
def search(x, A):
    L = 0
    R = N - 1
    while L <= R:
        M = (L + R) // 2
        if x < A[M]:
            print('求める要素{}は、要素{}({}番目)より小さい'.format(x, A[M], M))
            R = M - 1
        if x == A[M]:
            print('求める要素{}は、要素{}({}番目)と同じ'.format(x, A[M], M))
            return M
        if x > A[M]:
            print('求める要素{}は、要素{}({}番目)より大きい'.format(x, A[M], M))
            L = M + 1
    return - 1 # 整数 x が存在しない（注：この問題の制約で -1 が返されることはない）

# 二分探索を行う
Answer = search(X, A)
print('解：', Answer + 1)  # 配列が 0 番目から始まるので、答えに 1 を足す

[実行結果（入力例１）]

求める要素47は、要素37(7番目)より大きい

求める要素47は、要素53(11番目)より小さい

求める要素47は、要素43(9番目)より大きい

求める要素47は、要素47(10番目)と同じ

解： 11

[実行結果（入力例２）]

求める要素80は、要素50(4番目)より大きい

求める要素80は、要素80(7番目)と同じ

解： 8

二分探索では１回の判定で探索範囲が半分になるので、配列の長さを $ N $ とするとき、$ \log_2 N $ の比較を行うことになります。

つまり計算量は $ O(\log N) $ となります。