这种递归二分搜索算法可以更有效吗？

Question

我见过很多这种算法的不同实现，但我想知道除了使搜索二进制之外是否还有提高效率的方法。我设计了这个特定版本的算法，因此将立即检查 array/list 的边缘和中点以查找正在搜索的密钥，以避免在您查找的密钥只是第一个时循环搜索、中间或最后一个元素。

def searchRB(the_array, the_key, imin, imax):
    print("searching")
    found = False
    if (0 > the_key or the_key > len(the_array)):
        return found
    else:
        imid = imin + ((imax - imin) // 2)
        if imid == the_key or imin == the_key or imax == the_key:
            found = True
            return found
        elif the_array[imid] > the_key:
            return searchRB(the_array, the_key, imin, imid-1)
        elif the_array[imid] < the_key:
            return searchRB(the_array, the_key, imid+1, imax)
        else:
            return found

例如，如果您要在 1-100 的列表中查找数字 1，这将在第一个循环中找到它，这与其他一些实现不同。

但是，我不确定这是否真的提高了效率（某些边缘情况除外），并且一旦您检查 list/array 中的第一个、中间和最终值实际上是有害的继续循环，每次都必须检查这三个值。

这种算法的实现是好是坏，还是我只是吹毛求疵？

Answer 1

主要的大问题是从递归方法改为使用 while 循环，从而节省调用堆栈（因为 python 没有尾递归）。

您有可以优化的小冗余。算法已经足够优化，不要over optimise 除非你了解编译器

如果你沿着左边的树向下走，你将一遍又一遍地比较相同的 imin，但是整行可能是并行的或顺序完成的

if the_array[imid] == the_key or the_array[min] == the_key or the_array[imax] == the_key:

此外，这可能会影响缓存性能，因为您将 the_array[min] 始终保存在缓存中。有时，编译器会在您尝试在缓存中访问的索引周围的数组中存储一个块。你浪费的缓存可能比仅仅为那 1 个值还要多。

也可以优化像这样的语句，您可以只键入 return True，但这应该由编译器拾取。

found = True return found

不将 found 作为对象会优化代码，因为该对象不会一直存储在内存中。

这个 else 语句似乎是多余的，因为没有可能到达那个 else else return found

实际相关的优化将来自对数据集的更多了解。

如果您能够预处理数据（或了解有关数据的更多信息），则可以执行其他算法。

这种递归二分搜索算法可以更有效吗？

Could this recursive binary search algorithm be more efficient?

python

algorithm

recursion

binary-search