http://katemats.com/interview-questions/二进制搜索算法的说：性能时，有很多重复
给你一个有序数组，你想尽快找到你怎么做搜索的数量N. （不只是遍历每个元素）？
- 如果数组中有大量重复项，算法的性能如何改变？
我的回答第一个问题是二进制搜索，这是O（的log（n）），其中n是阵列中元件的数量。
根据this answer，“在”元素K在A中不存在且小于A中的所有元素“的最坏情况下，”我们有最大log_2（n-1）个步骤“。
我认为第二个问题的答案是它不会影响性能。它是否正确？
我不认为有重复的事情。
你正在寻找一个特定数量N，重要的是当前节点是否匹配N.
如果我期待在列表中的号码1 1-2-3-4- 5-6的表现与搜索1-9-9-9-9-9列表相同。
如果数字N重复，那么您将有机会尽快找到它的几个步骤。例如，如果在列表1-1-1-1-1-9上进行了相同的搜索。
如果你说的是最坏情况/大O，那么你是正确的 - log（n）是你的约束。但是，如果您的数据分布相当均匀（或者您可以映射到该分布），那么插入分区的位置可以获得日志（log（n））行为。当你进行插值的时候，你也可以摆脱你在寻找最终元素之一的情况下的糟糕情况（当然，尽管有新的病理情况）。
对于许多许多重复项目，您可能愿意在下一个探测器上进一步迈进直接中心。随着更多的嘟，，你有更好的猜测正确的边缘。虽然总是选择中途点在适当的时间让你在那里，但受过教育的猜测可能会给你一些非常出色的平均表现。
当我面试时，我喜欢听到这些答案，既有关于本书的知识，又有什么理论，还有什么事情可以做，以专注于给定的情况。通常这些常量因素可能会非常有用（请参阅快速排序及其分区选择方案）。