Pythonで2分探索法

今回は例として、

【3,5,7,9,11,13,15,17,19,21,23,25,27】

の数字列の中から「１１」を、2分探索法で探し出すプログラムを考えます。

※2分探索法は、(大きい順)　または　(小さい順)に整列されている必要があります。

2分探索法とは？

「探索値」と「探索範囲の中心」を比較して、大きいか小さいかで2等分する範囲を決める探索法です。

ｎ個のデータがある場合、

平均比較回数｜log2n 回

プログラム例

Pythonで2分探索法をプログラムすると、どうなるか見ていきます。

数字列【3,5,7,9,11,13,15,17,19,21,23,25,27】 から、「１１」を探し出すプログラムです。

a = [3,5,7,9,11,13,15,17,19,21,23,25,27]
i=1
l=11
j=len(a)
while i<j:
    m=((i+j)//2)
    if l>a[m-1]:
        i=m+1
    else:
        j=m
        
if a[i-1] == l:
    print(i)

プログラムの解説