二进制搜索程序不起作用，因为 expected.What 的错误？

Question

我在我的程序中得到的值是 "None"？我哪里出错了？

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))

提前appreciated.Thanks任何帮助！

Answer 1

在你的函数结束时，你需要 return 调用函数 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

Answer 2

存在三个错误-

首先如评论中所述和您写的答案之一 - binary_search(i) 而不是 return binary_search(i)
其次是逻辑错误。如果元素不在列表中，您的代码将运行进入无限循环。为避免此检查 start > end，如果 ti 发生则元素不存在。
第三次将 end 初始化为 len(lis2) ，如果您尝试搜索列表中不存在且大于最大值的元素，这将给出 IndexError: list index out of range列表中的元素（比如 23 ）。所以将 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))

二进制搜索程序不起作用，因为 expected.What 的错误？

Binary search program doesn't work as expected.What's wrong?

algorithm

binary-search

python-3.x