二分探索(?)を書く

やったこと

Pythonで二分探索を書いた。

なぜやったか

某書籍を読んでたら二分探索の話題が出てきて、昔書いたけどどんなのだったか忘れたので書いた。

コード

二分探索

def binary_search(data,search_n,m,n):  
    print("n:m",m," : ",n)  
    print("==>",data[m]," : ",data[n])  
    if n-m==1:
        print("sorry...XP")
        return -1
    else:
        center=(m+n)//2
        if data[center]>search_n:
            print("look at the bigger num : ",center," ==> ",data[center])
            return binary_search(data,search_n,m,center)
        elif data[center]<search_n:
            print("look at the smaller num : ",center," ==> ",data[center])
            return binary_search(data,search_n,center,n)
        else:
            print("ATTA : index is ",center," ==> ",data[center])
            return center
    

データの生成

import random
data=list(range(0,100))
random.shuffle(data)
data=data[10:71:2]
data.sort()
print(data) #[2, 5, 6, 7, 11, 13, 14, 15, 16, 17, 19, 21, 24, 30, 35, 42, 45, 54, 58, 62, 68, 70, 77, 78, 80, 83, 89, 92, 94, 98, 99]

実行

num=int(input())
print(binary_search(data,num,0,len(data)-1))
# 68
n:m 0  :  30
==> 2  :  99
look at the smaller num :  15  ==>  42
n:m 15  :  30
==> 42  :  99
look at the bigger num :  22  ==>  77
n:m 15  :  22
==> 42  :  77
look at the smaller num :  18  ==>  58
n:m 18  :  22
==> 58  :  77
ATTA : index is  20  ==>  68
20

エラー

RecursionError: maximum recursion depth exceeded
Pythonで設定されている再帰処理最大回数を超えると出てくるエラー。