配列の二分探索

問題

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

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

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

[制約]
🔹1≦N≦100000
🔹1≦A1<A2<…<AN≦109
🔹探す整数 X は A1,A2,…,AN のいずれかである

解き方・ソースコード

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

🔹M=(L+R)/2 とする（割り切れない場合は切り捨てる）
🔹X<AM の場合：探索範囲を左半分にする（R の値を M−1 にする）
🔹X=AM の場合：答えは M である
🔹X>AM の場合：探索範囲を右半分にする（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 とするとき、log2⁡N の比較を行うことになります。

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