algorithm - 对数组中的重复元素进行二分查找

Question

我想知道我们如何使用二进制搜索处理数组中的重复元素。例如，我有一个像 1 1 1 2 2 3 3 这样的数组。我有兴趣寻找 2 的最后一次出现。

根据之前看过的一个帖子，我们可以先用二分查找找到2，然后扫描相邻的元素。这大约需要 o(log(n)+k)。所以最坏的情况是当 k = n 时。然后它需要 O(n) 时间。有什么办法可以提高最坏时间的性能。谢谢。

Answer 1

对 2.5 进行二进制搜索.换句话说，如果您要搜索的值是 N , 那么你的代码应该对待 N就像它太小了，N+1就像它太大了。该算法的主要区别在于它不能幸运地提前终止(当它找到值时)。它必须一直运行到最后，当 high和 low指标相等。届时，您查找的索引与最终 high/low 的差值不应超过 1。索引。