二进制搜索程序无法按预期工作。怎么了？

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，如果ti发生，则元素不存在。
• 第三，您将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

在函数的末尾，你需要在调用函数递归时返回结果：

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