二分搜索递归python

Question

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

我尝试在vsc终端中运行，但出现语法错误。同时，problems选项卡没有显示任何错误。会很感谢你的指点的！

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)