我想知道我们如何使用二进制搜索处理数组中的重复元素。例如,我有一个像 1 1 1 2 2 3 3 这样的数组。我有兴趣寻找 2 的最后一次出现。
根据之前看过的一个帖子,我们可以先用二分查找找到2,然后扫描相邻的元素。这大约需要 o(log(n)+k)。所以最坏的情况是当 k = n 时。然后它需要 O(n) 时间。有什么办法可以提高最坏时间的性能。谢谢。
最佳答案
对 2.5
进行二进制搜索.换句话说,如果您要搜索的值是 N
, 那么你的代码应该对待 N
就像它太小了,N+1
就像它太大了。该算法的主要区别在于它不能幸运地提前终止(当它找到值时)。它必须一直运行到最后,当 high
和 low
指标相等。届时,您查找的索引与最终 high/low
的差值不应超过 1。索引。
关于algorithm - 对数组中的重复元素进行二分查找,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38405524/