javascript - 在不到 O(n) 的时间内找到(排序的)数组中的重复元素？

Question

我想知道是否可以在 O(log n) 中对 JavaScript 数组执行二进制搜索以查找单个重复元素。

// Example
  // Input: var arr = [1, 3, 4, 4, 6, 9, 11, 12, 14]
  // Output: 4

我知道如何在线性时间内解决这个问题，但我一直在尝试在 O(log n) 中编写一个解决方案，除非我不确定如何减少要搜索的数组 block 每次迭代。有什么建议吗？

Answer 1

只有当您知道要查找的元素时(或者，更准确地说，如果您在选择轴心点时可以分辨出它位于哪一半)，二分查找才有效。 p>

您的问题中没有任何内容似乎表明您具备这方面的知识，因此，基于此，O(n) 是您目前所能做到的最好的。

如果有一些额外的信息，则可能是这样的，比如一个范围内的所有数字都被表示，除了一个，或者重复的在特定范围内。

然而，根据目前的信息，情况并非如此。