在渐近分析的情况下，迭代和递归二分查找算法有什么区别？

Question

我需要展示迭代和递归二分查找算法渐进运行时间分析的差异。据我所知，它们的最坏情况复杂度相同（O(log(n))），但在一些资源中，递归算法的复杂度为 O(log(n)+1)。我有点困惑，能否有人帮我解决这个问题？

另外，我需要改进一个Python递归二分查找算法，使其与迭代算法一样快。下面是代码。

谢谢！

def binarySearch(alist,item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist)/2
        if alist[midpoint] == item:
            return True
        else:
            if item<alist[midpoint]:
                return binarySearch(alist[:midpoint],item)
            else:
                return binarySearch(alist[midpoint+1:],item)

- minyatur

---

这是关于class的吗？如果是，你应该在问题中注明。至于改进实现，你采取了哪些步骤？ - outis

这个问题是为了理解这两种算法的行为，这将帮助我理解并回答我的作业问题 :) 因此，这不是直接针对课堂的，但会帮助我理解并回答作业问题。 - minyatur

顺便说一句，我没有做任何改进，所以我在询问 :) - minyatur

“步骤”不仅包括具体的代码改进，还包括您为解决问题所做的任何努力，这表明a）您正在积极尝试，b）您遇到了哪些困难。 - outis

我看到的想法已经在上面的帖子下面写成了评论。我不明白为什么你要这么强烈地质疑。我说过这不是作业，我知道如何提问作业问题，我已经阅读了规则。别担心 :) - minyatur

Answer 1

O(log(n) + 1)与O(log(n))相同--在渐进意义下，它们产生相同的函数集。常数加法被忽略，就像常数倍数一样。

它们在空间使用上有所不同--递归二分查找将使用log(n)空间（由于堆栈），除非编译器删除尾调用并将其转换为非递归定义。

无论如何，由于切片非常昂贵（O(n)），您的算法在性能方面会大幅度失利。

- Devin Jeanpierre

---

我明白了，那我怎么能更好地切片呢？ - minyatur

我正在考虑添加更多参数，如“列表、值、第一个、最后一个”，并在每次调用时更改第一个和最后一个参数。这个解决方案怎么样？ - minyatur

或者我可能会更改外部else块内的内容，只是为了检查中点元素是否与第一个元素相等。 - minyatur

@theminyatur 第一次修改很好。第二次修改会使算法失去正确性，除非你做得对。 - Devin Jeanpierre

我实现了第二个选项，并使用内置的时间计算方法进行了检查。看起来它有效了 :) - minyatur