二分查找递归 python

Question

我是数据结构的新手，想问一下为什么我的二进制搜索给我一个错误。

我已经在 vsc 终端中尝试运行，但出现语法错误。同时，问题选项卡没有显示给我任何错误。不胜感激指点！

def binarysearch(list,value):
    if list == [] or (len(list)==1 and list[0]!= value):
        return False
    else:
        mid = list[len(list)/2]
        if mid == value:
            return True
        elif mid > value:
            return binarysearch(list[:len(list)/2],value)
        else:
            return binarysearch(list[len(list)/2+1:],value)

a =[1,2,3,4,5,6,7,8]
value = 7

if binarysearch(a,value):
    print("found")
else:
    print("none")

Answer 1

问题出在您调用递归的行中，要拆分的索引必须是整数而不是浮点数。试试下面的代码 -

def binarysearch(list,value):
    if list == [] or (len(list)==1 and list[0]!= value):
        return False
    else:
        mid = list[int(len(list)/2)]
        if mid == value:
            return True
        elif mid > value:
            return binarysearch(list[:int(len(list)/2)],value)
        else:
            return binarysearch(list[int(len(list)/2)+1:],value)

a =[1,2,3,4,5,6,7,8]
value = 7

if binarysearch(a,value):
    print("found")
else:
    print("none")

Answer 2

代码的索引部分有问题尝试使用 //（整数除法）符号而不是除法来获得除法后的近似值而不是小数（浮点数）：

def binarysearch(list,value):
if list == [] or (len(list)==1 and list[0]!= value):
    return False
else:
    mid = list[len(list)//2] # approximating the division to get an integer
    if mid == value:
        return True
    elif mid > value:
        return binarysearch(list[:len(list)//2],value)
    else:
        return binarysearch(list[len(list)//2+1:],value)

二分查找递归 python

Binary search recursive python

python

recursion

binary-search