二进制搜索小错误 Python 3.5

Question

我正在为 class 创建二进制搜索。

它应该显示 True 或 False，具体取决于该值是否在列表中。

我无法准确无误地获取最后一个元素，到目前为止我的代码：

def binarySearch(alist, value):
    first = 0                               
    last = len(alist)-1                                                  
    found = False                           

    while first <= last and not found:                    
        midpoint = (first + last)//2        
        print(midpoint)                     
        if value == midpoint:
            found = True
        else:
            if value < alist[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1

    return found


print(binarySearch([1,2,3,4,5],5))

行：last = len(alist)-1 无法识别列表中的最后一个元素？它转到前一个，所以，如果我运行上面的代码应该 return False 应该 return True.

我尝试了 last = len(alist)，这给了我最后一个元素，但是如果我尝试搜索大于 5 的数字，它会导致 IndexError 而不是显示 False。

有什么想法吗？

Answer 1

您正在根据索引 midpoint 检查值，而不是数组中的值。

if value == midpoint:

应该改为：

if value == alist[midpoint]:

二进制搜索小错误 Python 3.5

Binary Search small error Python 3.5

python

function

binary-search

python-3.x