二分探索

独学で初めて最近自分のプログラムが遅いという壁に当たり
アルゴリズムを勉強し始めました。

まずは、アルゴリズム入口??の二分探索を実装してみました。

python3.6

#二分探索
def binary_search(arry, item):
    low = 0
    high = len(arry) - 1#リストの長さを測定する
    
    #lowとhighが一致するか、ひっくり返るまで検索
    while low <= high:
        mid = (low + high) // 2#真ん中の要素の位置が整数になるように計算する
        
        if arry[mid] == item:#値が同じなら場所を返して終了
            return(mid)
        
        elif arry[mid] > item:#大きすぎたら半分より前を再度検索
            high = mid - 1
        
        else :#小さすぎたら半分より後を再度検索
            low = mid + 1
    
    return(None)#一致するものがなければNoneを返す

適当なリストを作って試してみます。

#適当なリストの作成
arry = list(range(0, 10,2))
#[0, 2, 4, 6, 8]

#検索するitem
item = 4

#二分探索
print(binary_search(arry, item))
#2

処理時間を測定しました。
10個の要素から検索するのに245ns
1億個の要素から検索するのに3.72µs

要素の個数は1000万倍だけど、処理時間は15倍!!

このアルゴリズムを知ってから
アルゴリズムをもっと知りたい！！勉強したい！！と思いました。