这种递归二进制搜索算法能更有效吗？

Question

我已经看到了这个算法的很多不同实现，但是我想知道除了将搜索变成二进制之外，是否还有其他方法可以提高效率。我设计了这个特殊版本的算法，这样就可以立即检查数组/列表的边缘和中点，以便在查找的键只是第一个、中间或最后一个元素时避免在搜索中循环。在

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中的first、mid和end值是否真的有害，只要您继续循环并且每次都要检查这三个值。在

这是这类算法的好是坏实现，还是我只是在分裂头发？在

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:

此外，这可能会影响缓存性能，因为您将始终将_数组[min]保存在缓存中。有时编译器会将数组中的块存储在缓存中试图访问的索引周围。 你可能会浪费更多的缓存，而不仅仅是为了这个1值。在

同样，像这样的语句也可以被优化，你只需输入return True，但是编译器应该再次选择它。在

found = True return found

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

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

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

如果你能预处理数据（或者有更多关于数据的信息），你可以做其他的算法。在