在小于O(n)时间内找到(排序)数组中的重复元素

Finding the duplicate element in a (sorted) Array in less than O(n) time?

本文关键字：数组元素排序小于时间更新时间：2023-09-26

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

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

我知道如何在线性时间内解决这个问题，但我一直试图在O(log n)中写出一个解决方案，除了我不确定如何在每次迭代中减少数组的块来搜索。任何建议吗?

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

你的问题中似乎没有任何东西表明你有这些知识，因此，基于此，O(n)是你目前能做的最好的。

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

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