python - 二分搜索递归实现

Question

我正在尝试创建我的二进制搜索的递归版本的实现。这就是我到目前为止所拥有的。任何人都可以帮助我不知道如何完成。

def binarySearch(searchList, numberSought, low, high):
    if high < low:
        return False
    midpoint = (low + high)//2
    print ("high is index", high)
    print ("low is index", low)
    print ("midpoint is index", midpoint)
    if searchList[midpoint] == numberSought:
        return True
    elif ...

    else:
        ...

mylist = [2, 4, 7, 13, 21, 22, 27, 31, 41, 77, 97, 144, 168]
first = 0
last = len(mylist) - 1
candidate = int(input("Does our list contain the following number? "))
print ("It is ",binarySearch(mylist,candidate,first,last), "that our list contains", candidate)

Answer 1

您的下一步是填写以下空白：

    if searchList[midpoint] == numberSought:
        return True
    elif searchList[midpoint] < numberSought:
        pass # somehow search left of midpoint here
    else: # must have > numberSought
        pass # somehow search right of midpoint here

这有帮助吗？

Answer 2

你可以使用这个递归程序..来执行二分搜索。

>>>def BS(list,key,min,max):
    if max<min:
        return None
    else:
        mid=(min+(max-min)/2)
    if list[mid]>key:
        return BS(list,keyey,min,mid-1)
    elif list[mid]<key:
        return BS(list,key,mid+1,max)
    else:
        return mid

>>> min = 0
>>> list = [2, 4, 7, 13, 21, 22, 27, 31, 41, 77, 97, 144, 168]
>>> max = len(list)-1
>>> key = 21
>>> BS(list,key,min,max)

wiki 说：二进制搜索或半间隔搜索算法在按键值排序的数组中查找指定输入值（搜索“键”）的位置。[1][2] 在每一步中，算法都会将搜索键值与数组中间元素的键值进行比较。如果键匹配，则已找到匹配元素并返回其索引或位置。否则，如果搜索关键字小于中间元素的关键字，则算法在中间元素左侧的子数组上重复其操作，或者如果搜索关键字更大，则在右侧的子数组上重复其操作。如果要搜索的剩余数组为空，则无法在数组中找到键并返回特殊的“未找到”指示。

Answer 3

为什么不查看 Python bisect 模块中非递归但规范实现的源代码？当然，您必须将 while 循环转换为递归。