Python 中的递归二进制搜索

Question

我试图理解这个函数，但几乎没有结果。我完全理解二分查找是什么，但对递归的概念还不熟悉，但对它略有了解。我真的不明白第一次调用函数时 low 和 high 的默认值是多少。截至目前，我只包括搜索 space 我知道号码在其中，但如果我不知道或不确定列表长度怎么办？否则，我理解这里进行的递归过程以及对低级和高级参数的需求。以下功能是我正在上的在线课程的笔记中提供的；然而，它没有在讲座中解释，也不包含关于它的文档字符串或参考资料。

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 不包含在搜索中space。在第二个示例中，84 的索引为 5，因此它包含在搜索 space 中，跨越索引 0 和 6.

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

print bSearch(L, 84, 0, 5)

答案是：

True

如果你想搜索整个列表，你可以简单地做：

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

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

Answer 2

二分查找。

bsearch(列表，要查找的元素，开始索引，结束索引)。 start index 在函数开始时可以取0 最后一个索引可以作为 len(list)-1

关于 bsearch(L,15, 4, 8) 的问题。你只在第 5 和第 9 个元素之间搜索，其中数字不存在。

在第二个函数调用中，您正在第一个元素和第 5 个元素之间搜索数字。

对于任何其他数字，您可以将此函数称为 bsearch(L , 15 ,0 , len(L) - 1)。

希望对您有所帮助。

Answer 3

low 和 high 指定算法必须搜索的 L 的索引。在第一个示例中，15 的索引为 3。这不在区间 [4,8] 中，因此它将 return false。在第二个示例中，L 中 84 的索引为 5，这是在区间 [0,6] 中，因此这将 return True.

如果您要搜索的号码不在 L 中，此方法将 return False。为什么？因为您最终处于 if (high-low) < 2 的基本情况。在这种情况下，将检查 L[high] or L[low] 是否等于您要搜索的数字。如果两者都不是的话，那就returns False。这是逻辑 or.

的定义

False or False = False False or True = True True or False = True True or True = True

如果您不确定列表长度，如果您提供的 high 或 low 值不在 L 范围内，这将产生错误。您可以添加一个额外的条件，这样就不会发生这种情况，但我认为这超出了该课程的范围。 :)

Python 中的递归二进制搜索

Recursive binary search in Python

python

recursion

binary-search