アルゴリズム？プログラミング。 - 探そう！2分探索

順番に並んだリストの中から目的の数字を探すアルゴリズムです。

考え方としては、

１　リストの真ん中の値が探している値であるかどうか

真ん中の値ではない場合は

２　その探している値が真ん中の値より大きいか小さいかでリストの幅を変
　　えていきます。

コードで確かめていきます。

array = [3,7,8,10,12,25]

このリストから

serch = 12

"12"を探します。

まずリストの範囲、リストの左はしのインデックスと右はしのインデックスを調べます。

左はし(left)は"0"で決まりですが、右はし(right)はリストの長さ(len()を使います)を調べます。長さを調べているので、最後のインデックスとしては"-1"した数になります。

left = 0

right = len(array) - 1

あとは半分処理を繰り返して真ん中の値が探している数字と合致すれば終了です。

whileを使います。その条件は

while left <= right:

で、右側のインデックスが左のインデックスより小さくならなければループが続きます。

そして真ん中の値を調べて、同じかどうか調べます。

 middle = (left + right)//2

"//"を使うことで割り切れなくても整数にしています。

次に真ん中の値が調べている値かどうか調べます。

 if array[middle] == serch:
        print(f"indexは {middle}")
        break

探している数字と同じものがあれば終了します。

ここで見つからない場合、

調べた真ん中の値より探している数字が大きければ左はしのインデックスの"left"の数字を真ん中のmiddleより大きくします( middle + 1)。

 elif array[middle] < serch:
        left = middle + 1

逆の場合は右はしのインデックスを真ん中とりも小さくします(middle - 1)。

    else:
        right  = middle - 1

この処理を真ん中の値と同じになるまで繰り返します。

全体としては

array = [3,7,8,10,12,25]


serch = 12

left = 0
right = len(array) - 1


while left <= right:
    middle = (left + right)//2

    if array[middle] == serch:
        print(f"indexは {middle}")
        break
    elif array[middle] < serch:
        left = middle + 1

    else:
        right  = middle - 1