我想知道是否有可能在JavaScript数组上执行O(log n)二进制搜索以查找单个重复元素。
// Example
// Input: var arr = [1, 3, 4, 4, 6, 9, 11, 12, 14]
// Output: 4
我知道如何在线性时间内解决这个问题,但我一直试图在O(log n)中写出一个解决方案,除了我不确定如何在每次迭代中减少数组的块来搜索。任何建议吗?
只有当知道要查找的元素时(或者,更确切地说,当您选择了轴心点时,如果您可以知道它在哪一半中),二分查找才有效。
你的问题中似乎没有任何东西表明你有这些知识,因此,基于此,O(n)
是你目前能做的最好的。
如果有一些额外的信息,这可能是可能的,比如一个范围内的所有数字都被表示,除了一个,或者重复的数字在一个特定的范围内。
然而,根据目前的信息,情况并非如此。