【出典】「新・明解Pythonで学ぶアルゴリズムとデータ構造」
前回の記事はこちら
3-3 2分探索
今回はソート済みのものを前提に考えます。用途は限定的ですが、線形探索よりもはるかに高速な探索ができるそうです。
2分探索
2分探索は要素がキーの昇順または降順にソートされている配列から効率よく探索を行うアルゴリズムです。
※ソートのアルゴリズムは6章らしいです。(遠いなあ)
a = [5, 7, 15, 28, 29, 31, 39, 58, 68, 70, 95]を想定して、39の探索を考えます。
この時中央に位置する要素a[5] == 31 に着目します。
目的とする39は、この要素よりも末尾側に存在すると仮定してa[6]～a[10]に着目します。
さらにa[6]～a[10]の中央a[8]に着目。
目的とする値はa[8]よりのため、a[6]、a[7]に絞ります。
二つの要素の中央要素として、39に着目します。((6 + 7) // 2 が6となるため)
着目した39は目的のキーなので、探索成功となります。
#2分探索
from typing import Any, Sequence
def bin_search(a: Sequence, key: Any) -> int:
"""シーケンスaからkeyと一致する要素を2分探索"""
pl = 0 #探索範囲先頭の添字
pr = len(a) - 1#探索範囲末尾の添字(添字が0-10ならlen(a)は11)
while True:
pc = (pl + pr) // 2 #中央要素の添字
if a[pc] == key: #keyとリストaのpc番にある値が一致したら
return pc #探索成功
elif a[pc] < key: #keyよりリストaのpc番にある値が小さいなら
pl = pc + 1 #探索範囲を後半に絞り込む
else: #それ以外は
pr = pc - 1 #探索範囲を前半に絞り込む
if pl > pr: #もし先頭の添字が末尾の添字よりも大きいなら
break #終了する
return -1 #探索失敗
if __name__ == '__main__':
num = int(input('要素数：'))
x = [None] * num #要素数numの配列を生成
print('昇順に入力してください')
x[0] = int(input('x[0]:'))
for i in range(1, num):
while True:
x[i] = int(input(f'x[{i}]:'))
if x[i] >= x[i - 1]: #値が一つ前の数字以下の場合
break
ky = int(input('探す値：')) #キーkyの読み込み
idx = bin_search(x, ky) #kyと等価な要素をxから探索
if idx == -1: #関数bin_searchから返ってくる値
print('その値の要素は存在しません。')
else:
print(f'その値は[x{idx}]にあります。')
2分探索アルゴリズムでは必要となる比較回数の平均はlog nとなります。
計算量
アルゴリズムの性能を客観的に評価するための尺度として計算量を使います。(時間計算量と領域計算量の2つ)
線形探索の時間計算量
次のプログラムを例に考えます。
def seq_search(a: Sequence, key: Any) -> int:
i = 0 #①
while i < n: #②
if a[i] == key: #③
return i #④
i += 1 #⑤
return -1 #⑥
table3-1:線形探索における各ステップの実行回数と計算量
| ステップ | 実行回数 | 計算量 |
|---|---|---|
| ① | 1 | O(1) |
| ② | n/2 | O(n) |
| ③ | n/2 | O(n) |
| ④ | 1 | O(1) |
| ⑤ | n/2 | O(n) |
| ⑥ | 1 | O(1) |
OはオーダーのOです。O(1)に要する計算時間は変化しませんが、O(n)に要する計算時間はnに比例して長くなります。
計算量は O(f(n))+O(g(n))=O(max(f(n),g(n))) で表すことができ、先ほどのプログラムの計算量を計算すると、
O(1)+O(n)+O(n)+O(1)+O(n)+O(1)
=O(max(1,n,n,1,n,1))
=O(n)
となります。
| コラム3-2 indexメソッドによる探索 |
|---|
indexメソッドを使うことで、リストやタプルから探索が可能です。呼び出し方は
obj.index(x, i, j)
でobj[i:j]内にxと等価な要素が含まれれば、その最小の添字が返却される。含まれない場合はValueError例外が送出されます。
2分探索の時間計算量
2分探索アルゴリズムの計算量を求めるとO(log n)となります。
log nといってもピンとこないと思うのでいろんな計算式を羅列すると
1 < log n < n < nlog n < n**2 < n**3 < n**k < 2**n
となります。
| コラム3-3 2分探索の途中経過の表示 |
|---|
list3-4の関数部分を改良して、探索過程を表示するように変更したものです。
参考にしたものと結果がやや違うのですが、理屈はなんとなく抑えたのでよしとします。
#2分探索の様子を表示
from typing import Any, Sequence
def bin_search(a: Sequence, key: Any) -> int:
"""シーケンスaからkeyと一致する要素を2分探索"""
pl = 0 #探索範囲先頭の添字
pr = len(a) - 1#探索範囲末尾の添字(添字が0-10ならlen(a)は11)
#ここから追加分
print(' |', end = '')
for i in range(len(a)):
print(f'{i:4}', end = '')
print()
print('---+' + (4 * len(a) + 2) * '-')
#ここまでが追加された部分
while True:
pc = (pl + pr) // 2 #中央要素の添字
#ここから追加分
print(' |', end = '')
if pl != pc:
print((pl * 4 + 1) * ' ' + '<-' + ((pc - pl) * 4) * ' ' + '+', end = '')
else:
print((pc * 4 + 1) * ' ' + '<+', end = '')
if pc != pr:
print(((pr - pc) * 4 - 2) * ' ' + '->')
else:
print('->')
print(f'{pc:3}|', end = '')
for i in range(len(a)):
print(f'{a[i]:4}', end = '')
print('\n |')
#ここまでが追加された部分
if a[pc] == key: #keyとリストaのpc番にある値が一致したら
return pc #探索成功
elif a[pc] < key: #keyよりリストaのpc番にある値が小さいなら
pl = pc + 1 #探索範囲を後半に絞り込む
else: #それ以外は
pr = pc - 1 #探索範囲を前半に絞り込む
if pl > pr: #もし先頭の添字が末尾の添字よりも大きいなら
break #終了する
return -1 #探索失敗
if __name__ == '__main__':
num = int(input('要素数：'))
x = [None] * num #要素数numの配列を生成
print('昇順に入力してください')
x[0] = int(input('x[0]:'))
for i in range(1, num):
while True:
x[i] = int(input(f'x[{i}]:'))
if x[i] >= x[i - 1]: #値が一つ前の数字以下の場合
break
ky = int(input('探す値：')) #キーkyの読み込み
idx = bin_search(x, ky) #kyと等価な要素をxから探索
if idx == -1: #関数bin_searchから返ってくる値
print('その値の要素は存在しません。')
else:
print(f'その値はx[{idx}]にあります。')
本日は以上ですありがとうございました。