为 Python 编写了递归和迭代版本的二进制搜索算法。你如何判断他们的效率？

Question

首先，让我告诉您我实际上是如何使用这些算法的，以免出现任何混淆，因为这不是二进制搜索算法的典型用法。

我需要这些函数用于纯粹的学术/测试目的，以便将速度与我测试过的其他函数进行比较，包括 Python 的内置 isinstance()和在方法/操作数中。

我正在检查一个包含数字和字母的字符串，并测试其中的字符是否为整数。

因此，以下算法在字符串上循环的每次迭代（即字符）上的应用是：

binSearch("0123456789", "4", 0, 10)

“4”只是举个例子。

binSearch2("0123456789", "w")

“w”只是举个例子。

注意： 我知道 bisect 模块的存在。不过，这不是我实验和练习的重点和目的。

#下面的递归版本

def binSearch(list, digit, low, up):

mid = (low + up) // 2
midd = list[mid]

if digit == midd:
    return True
elif digit > midd:
    if mid == 9: return False
    return True and binSearch(list, digit, mid, up)
elif digit < midd:
    return True and binSearch(list, digit, low, mid)

#以下迭代版本

def binSearch2(list, digit):

low = 0
up = len(list)
mid = (low + up) // 2

while mid > 0:

    if digit == list[mid]: 
        return True

    elif digit > list[mid]:
        low = mid
        if low == 9: break

    else:
        up = mid

    mid = (low + up) // 2
    #print(low, mid, up)

if digit == list[mid]: return True

return False

欢迎评论！

Answer 1

可以通过确保 mid 被排除在您在下一次传递（递归调用或后续循环）中考虑的索引范围之外来改进您的两个函数。由于您刚刚检查了 mid 索引是否具有您想要的值（但它没有），您可以通过将 low 设置为 [=15= 来从上限间隔中排除 mid ] 在下一关。它已经被排除在较低的间隔之外，因为 up 索引超出了间隔的末尾（它是半开的）。

您还将一个奇怪的基本故障案例硬编码到函数中，您在其中检查 mid==9。对于大量输入（例如较短的字符串），这将无法正常工作，并且可能导致您的代码永远运行，或者根据针字符相对于 haystack 字符串中字符的位置引发异常（尝试使用您当前的代码搜索 ' '）。正确的基本情况测试是 low >= up，这表明您的搜索区间为空。对于迭代代码，只要 low < up.

就会一直循环

以下是我更新您的函数的方式：

def binSearch(list, digit, low, up):
    if low >= up:        # base case moved here, tested properly
        return False
    mid = (low + up) // 2
    midd = list[mid]
    if digit == midd:
        return True
    elif digit > midd:   # no more base case code in this block
        return binSearch(list, digit, mid+1, up)   # exclude mid from the next interval
    elif digit < midd:
        return binSearch(list, digit, low, mid)


def binSearch2(list, digit):
    low = 0
    up = len(list)
    while low < up:  # base case test is here now
        mid = (low + up) // 2  # move this here, so we don't need to repeat it
        if digit == list[mid]: 
            return True
        elif digit > list[mid]:
            low = mid + 1      # skip mid when moving up, no longer test base case here
        else:
            up = mid
    return False

为 Python 编写了递归和迭代版本的二进制搜索算法。你如何判断他们的效率？

Wrote Binary Search algorithms for Python, both a recursive and iterative version. How would you judge their efficiency?

python

iteration

recursion

performance

binary-search