二分探索①(全4回)

二分探索とは

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

基本

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

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

問題

昇順にソートされた数列から、ある数字k以上となるような最小の

インデックス(数字の位置)を求めてください。

ソースコード

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

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

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

こうすることにより、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
#----- 入力例1 -----
lst = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
k = 5
#----- 入力例2 -----
# lst = [-10,4,6,100,200,400,500]
# k = 10
#----- 入力例3 -----
# 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)

[実行結果](入力例1)

解 4

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

[実行結果](入力例2)

解 3

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

[実行結果](入力例3)

解 30000

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

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