Python3で二分探索

授業だる&注意

アルゴリズムの授業で二分探索を書かされたので、Python3にて実装。
下の配列に対して破壊(要素の消去)を行なっているため、実際に使う際にはデータのコピーをして実行するか、left,rightなどの変数を用いて条件を変更した方が良さそう。
それと関数化したほうが便利よねって思ったけど、Pythonはinを用いれば検索できるし、アルゴリズムの練習でコード化しただけだし別にいいやってなりました、はい。

ソースの解説

適当なlistを用意し、それを昇順にソートする。
探したい数値をsa_numに格納。
探索時に何度処理をしたかを数えるためにcntを使用。endは終了条件、sucは成功したかどうかのフラグとして使用。
endが0なら繰り返す
要素が1ならその要素だけ調べれば終わりなのでend = 1としてフラグ立てる。
そうでないなら、中央値を取得する。
中央値と探したい値が一致しなければ、中央値と探したい値の大小比較を行う。中央値の方が大きければ、探したい値は0からindexまで。つまり配列の右側(index~最後まで)は要らないので、スライスを用いて削除。逆に中央値より小さければ左側を削除。
もし、配列の要素数が1になってしまったら、その要素を取り出して探したい数値と比較する。探したい数値が見つからなければ終わり。

lis = [15,23,25,601,65,87,9,103,15,30,11,13]
lis.sort()

sa_num = 25

cnt = 0
end = 0
suc = 0

while end == 0:

    cnt += 1

    print(lis)

    if len(lis) != 1:

        index = int(len(lis) / 2)

        if lis[index] == sa_num:

            print('suc' + str(sa_num))
            end = 1

        elif lis[index] > sa_num:

            del lis[index:]

        elif lis[index] < sa_num:

            del lis[0:index]

    else:

        if lis[0] == sa_num:

            print(sa_num)
            end = 1

        else:

            print('見つかりませんでした。')
            suc = 1
            end = 1

if suc != 1:

    print(str(cnt) + '回目の探索で見つかりました。')

else:

    print(str(cnt) + '回探索をしましたが見つかりませんでした。')