python - Python 中的递归二分查找

Question

我试图理解这个函数，但几乎没有效果。我完全理解什么是二分搜索，但对递归的概念还很陌生，但对其有一些了解。我真的不明白第一次调用该函数时低和高的默认值是什么。截至目前，我只包括我知道该号码所在的搜索空间，但如果我不知道或不确定列表长度怎么办？否则，我理解这里发生的递归过程以及低和高参数的需要。以下功能是我正在参加的在线类(class)的笔记中提供的；但是，讲座中没有对此进行解释，并且不包含有关它的文档字符串或引用资料。

def bSearch(L, e, low, high):
    if high - low < 2:
        return L[low] == e or L[high] == e
    mid = low + int((high-low)/2)
    if L[mid] == e:
        return True
    if L[mid] > e:
        return bSearch(L, e, low, mid-1)
    else:
        return bSearch(L, e, mid+1, high)

L = [1,3,6,15,34,84,78,256]
print bSearch(L, 15, 4, 8)
print bSearch(L, 84, 0, 6)

输出:

False
True

Answer 1

最高价和最低价似乎是要搜索列表部分的索引。

在第一个示例中，15 的索引为 3，因此指定较低的索引 4 意味着 15 不包含在搜索空间中。在第二个示例中，84 的索引为 5，因此它包含在跨越索引 0 和 6< 的搜索空间中.

这些指数也包含在内。如果第二个例子是:

print bSearch(L, 84, 0, 5)

答案是:

True

如果您想搜索整个列表，您可以简单地执行以下操作:

print bSearch(L, 84, 0, len(L) - 1)

其中 - 1 是必需的，因为搜索功能是包容性的。