二分探索

2分探索は、ソートされたリストの要素を探索する速くて効果的な手法である。
最も効率的な探索戦略は、答えとなる可能性のある残された数字（上限と下限）のちょうど真ん中（中間点）の数字を推測し、その数字が探索している数字より大きいなら、その数値を新しい上限にする。逆に知以内なら、その数値を新し下限にする。以下、このプロセスを繰り返し、推測した位置の数字と探索している数字が一致する（差が1未満値）までこれを繰り返し、一致すれば探索が完了。

#二分探索プログラム例
import math
sortedcabinet = [1,2,3,4,5,6,7,8,9,10]

def binarysearch(sorted_cabinet,looking_for):
guess = math.floor(len(sortedcabinet)/2)
lowerbound = 0
upperbound = len(sorted_cabinet)

while(abs(sorted_cabinet[guess] – looking_for) > 0.0001):
if(sortedcabinet[guess] > looking_for):
upperbound = guess
guess = math.floor((guess + lowerbound)/2)
else:
lowebound = guess
guess = math.floor((guess + upperbound)/2)
return(guess)

print(binarysearch(sortedcabinet, 6))

 

上記だと、探索しようとした数字が探索する数字列の中にあれば、探索結果が見つけられるが、もし、探索する数字が探索する数字列の中になければ、このプログラムは終了しない。

 

 

参考とした書籍
署名：アルゴリズムをめぐる冒険–勇敢な初学者のためのPythonアドベンチャー
著者：Bradford Tuckfield
訳者：竹川文則、川上悦子、高柳愼一
発行所：共立出版(株)