Pythonを使用したバイナリ検索

Question

バイナリ検索のPythonアルゴリズムを試してみました。これは、リストにない値を検索する際に連続ループのエラーを表示しています。単にo/pに "not found"私が試したもう一つの方法はうまく機能していますが、機能の使用は許可されていません、私は間違いがないのですか？ O/Pで

M = [4,5,6,7,8,9,20,17,45] 
print(M) 
num = int(input("enter the number: ")) 
k=True 
low=0 
high=len(M)-1 
mid=(low-high)//2 
while low<=high: 
print(mid) 
if num == M[mid]: 
    print("Number found") 
    k=False 
    break 
else: 
    if num < M[mid]: 
     high = mid 
     mid = (low+high)//2 
     k=True 

    else: 
     low=mid 
     mid=(mid+high)//2 
     k=True 

if k==True: 
    print("not found") 

を表示[4、5、6、7、8、9、20、17、45] 番号を入力します。ために、例えば言う場合 を私が与えます私に無限ループを与えている25のように入力...

Answer 1

ねえ、あなたのコードにいくつかのミスがあり、

M = [4,5,6,7,8,9,20,17,45] # Your list is not sorted properly 
M.sort() 
print(M) 
num = int(input("enter the number: ")) 
k=True 
low=0 
high=len(M)-1 
mid=(low+high)//2 # you used (low-high) which is not the way to find the mid value 
while low<=high: 
print(mid) 
if num == M[mid]: 
    print("Number found") 
    k=False 
    break 
else: 
    if num < M[mid]: 
     high = mid - 1 # don't need to consider the mid value again 
     mid = (low+high)//2 
     k=True #you don't need to use this statement every loop 

    else: 
     low=mid + 1 # no need to consider mid again 
     mid=(low+high)//2 # should be low not mid 
     k=True 

if k==True: 
    print("not found") 

希望これはあなたを助けた:)

Answer 2

M = [4,5,6,7,8,9,20,17,45] 
M.sort() # added sort 
print(M) 

num = int(input("enter the number: ")) 
k=True 
low=0 
high=len(M)-1 

while low<high: 
    mid=(high+low)//2 # better place for mid calculating 

    if num == M[mid]: 
    print("Number found") 
    k=False # one k is enough in this while 
    break 
    else: 
    if num < M[mid]: 
     high = mid-1 # you don't need to recheck the mid value in future 
    else: 
     low = mid+1 # you don't need to recheck the mid value in future 

if k==True: 
    print("not found")