在数组中使用重复元素的二进制搜索

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。

Answer 2

最简单的方法是做一个上界二分搜索。这与您提到的二元搜索完全相同，除了不是试图找到数字的第一个实例，它首先是数字的第一个实例，它比所提供的更大。它们之间的区别仅仅是将<转换为<=。

一旦你找到一个大于你的数字的第一个实例，退一步索引，然后看看那里的值。如果它是2，那么你找到了最后的2个。如果是其他的，那么阵列中没有2。