二進制搜索程序無法按預期工作。有什麼問題？

Question

我在我的程序中獲得了「無」的價值？我哪裏錯了？

lis2 = [1, 3, 6, 2, 5, 4, 8, 12] 
lis2 = sorted(lis2) 
start = 0 
end = len(lis2) 
mid = (start+end)/2 

def binary_search(i): 
    global mid,start,end 
    if i==lis2[mid]: 
     return "Found" 
    elif i<lis2[mid]: 
     end = mid-1 
     mid = (start+end)/2 
    elif i>lis2[mid]: 
     start = mid+1 
     mid = (start+end)/2 
    else: 
     return "Not Found" 

    binary_search(i) 


print(binary_search(6)) 

任何幫助表示感謝。提前感謝！

Answer 1

三錯都存在 -

• 作爲註釋和一個提到的第一你寫的答案 - binary_search(i)而不是return binary_search(i)
• 其次是邏輯錯誤。如果元素不在列表中，您的代碼將運行到無限循環。爲避免這種檢查，如果start > end，如果發生，則元素不存在。
• 第三次初始化end到len(lis2)，如果您試圖搜索列表中不存在且大於列表中最大元素（比如23）的元素，則會給出IndexError: list index out of range。因此，改變end = len(lis2)到end = len(lis2)-1

正確的代碼 -

lis2 = [1, 3, 6, 2, 5, 4, 8, 12] 
lis2 = sorted(lis2) 
start = 0 
end = len(lis2)-1 
mid = int((start+end)/2) 

def binary_search(i): 
    global mid,start,end 
    if(start>end): 
     return "Not Found" 
    if i==lis2[mid]: 
     return "Found" 
    elif i<lis2[mid]: 
     end = mid-1 
     mid = int((start+end)/2) 
    elif i>lis2[mid]: 
     start = mid+1 
     mid = int((start+end)/2) 
    return binary_search(i) 

print(binary_search(6)) 

Answer 2

在你的函數結束時，你需要將結果返回調用函數recursivley時：

def binary_search(i): 
global mid,start,end 
if i==lis2[mid]: 
    return "Found" 
elif i<lis2[mid]: 
    end = mid-1 
    mid = (start+end)/2 
elif i>lis2[mid]: 
    start = mid+1 
    mid = (start+end)/2 
else: 
    return "Not Found" 

return binary_search(i) # <----- EDITED