algorithm - 存在大量重复项时二分查找算法的性能

Question

http://katemats.com/interview-questions/说:

• You are given a sorted array and you want to find the number N. How do you do the search as quickly as possible (not just traversing each element)?

  • How would the performance of your algorithm change if there were lots of duplicates in the array?

我对第一个问题的回答是二分查找，即 O(log(n))，其中 n 是数组中元素的数量。

根据this answer ，在最坏的情况下，当“元素 K 不存在于 A 中并且小于 A 中的所有元素”时，“我们最多有 log_2(n-1) 步”。

我认为第二个问题的答案是它不会影响性能。这是正确的吗？

Answer 1

如果你说的是最坏情况/大O，那么你是对的 - log(n) 是你的界限。但是，如果您的数据分布相当均匀(或者您可以映射到该分布)，则在选择分区的位置进行插值可以获得 log(log(n)) 行为。当您也进行插值时，您还可以摆脱寻找最终元素之一的最坏情况(当然，也有新的病理情况)。

对于许多重复项，您可能愿意在下一个探针上进一步远离直接中心。重复次数越多，你就越有可能正确猜测。虽然总是选择中间点可以让你及时到达那里，但有根据的猜测可能会让你得到一些非常出色的平均行为。

当我面试时，我喜欢听到这些答案，包括书本知识和理论是什么，还有可以做哪些事情来专门针对特定情况。通常这些常数因素确实很有帮助(看看快速排序及其分区选择方案)。