二分探索（全４回）

二分探索とは

二分探索 とは、解の存在範囲を狭めていくことにより最適解を求める手法（アルゴリズム）です。

二分探索で検索

二分探索 で解けるもっとも基本的な問題は、数列から 特定の数字を検索 する問題です。

数列は昇順にソートされている必要があります。

問題

昇順にソートされた数列から、ある数字ｋ以上となるような最小のインデックス（数字の位置）を求めてください。

ソースコード

処理としては、まず中央の値に着目します。

中央の値がｋ以上であれば 解が中央の位置よりも下 にあることがわかるので、上限の位置を中央に ずらします。

中央の値がｋ以下であれば 解が中央の位置よりも上 にあることがわかります、下限の位置を中央に ずらします。

こうすることにより、１回の比較で解の存在の範囲を 半分に絞る ことができます。

これ以降、句点の中点での比較を繰り返すことで解の存在の範囲を絞っていき解を求めます。

[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
#----- 入力例１ -----
lst = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
k = 5
#----- 入力例２ -----
# lst = [-10,4,6,100,200,400,500]
# k = 10
#----- 入力例３ -----
# lst = range(99999999999)
# k = 30000
#--------------------
n = len(lst)

# 解の存在範囲を初期化
lb = -1   # 下限の範囲
ub = n    # 上限の範囲

while ub - lb > 1:
    mid = (lb + ub) // 2
    if lst[mid] >= k:
        ub = mid
    else:
        lb = mid
print('解', ub)

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

解 4

インデックス4 の位置の数値は5であり、ｋと一致します。

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

解 3

数列に10は存在しませんが、インデックス3 の位置の数字100はｋ(=10)よりも大きくなります。

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

解 30000

非常に大きな数列 に対しても、二分探索であれば効率的に検索することができます。

次回からは 二分探索 を応用していろいろな問題を解いていきます。