バイナリーサーチについて

Question

第1引数に数字の配列、第2引数に探したい数字を取り、探したい数字が配列の何番目にあるか(=インデックス。0始まりとすること)を返し、見つからなければNoneを返す関数binary_searchを作成したいのですが、どこが間違っているでしょうか。（このプログラムは実行すると入力を待ち、数字を入力してEnterを押すと、binary_searchの第1引数に数字が小さい順にソート済みの配列numbersが、第2引数に入力された数字が与えられて実行され、返り値がprint()される。）

---

def binary_search(array, target):
# 初期探索範囲は配列の左端から右端まで
left_index = 0
right_index = len(array) - 1

while True:
    if left_index > right_index or (left_index + right_index) // 2 >= len(array):
        # 探索範囲がなくなったとき、数字は見つからなかったものとする
        return None

    center_index = (left_index + right_index) // 2
    if numbers[center_index] == target_num:
        right_index = center_index - 1
    elif numbers[center_index] < target_num:
        left_index = center_index - 1
    else:
        # 探索終了
        return center_index

numbers = [3, 7, 8, 9, 13, 17, 18, 20, 21, 24, 27, 29, 30, 33]
target_num = int(input())
result = binary_search(numbers, target_num)
print(result)

---

Comments

[itagagaki]

これは課題ですか？

[sgefueheiffd674]

はい

Answer 1

無限ループしていますね。

こういうバグの原因を知りたいときは、pdb --- Python デバッガかIDEを使うのですが、その使い方を覚える時間もないのであれば、logging --- Python 用ロギング機能を使うか、printデバッグで済ませましょう。

left_index,right_index,center_indexぐらいを見ていけば、原因は分かるでしょう。