algorithm - 具有数组中重复元素的二进制搜索

标签 algorithm binary-search

我想知道如何使用二进制搜索处理数组中的重复元素。例如,我有一个类似于11 1 2 2 3的数组我有兴趣寻找2的最后一次出现。
根据我之前读过的一篇文章,我们可以先用二进制搜索找到2,然后扫描相邻的元素这大约需要o(对数(n)+k)。所以最坏的情况是当k=n时,它需要o(n)时间。有什么方法可以改善最糟糕时期的表现吗?谢谢。

最佳答案

2.5执行二进制搜索。换句话说,如果您要搜索的值是N,那么您的代码应该将N视为太小,而将N+1视为太大该算法的主要区别在于它不能幸运地提前终止(当它找到值时)它必须一直运行到最后,当highlow索引相等时此时,您所寻找的索引与最终high/low索引的距离不应超过1。

关于algorithm - 具有数组中重复元素的二进制搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38405524/

相关文章:

algorithm - 二分查找

algorithm - 大O符号-递归函数

algorithm - 从多边形计算对偶图

algorithm - 对于二进制堆优先级队列,deleteMin访问多少个外部存储器 block ?

java - 使用字符串的通用二进制搜索

java - 二分搜索多个相同的项目并计数出现

python - 当已知因式分解中出现的素数(short〜)列表时,有哪些有效的因式分解算法?

c++ - 如何在 C 或 C++ 中以 O(n) 删除数组中的重复元素?

algorithm - NLP算法原理

Ruby#index 方法 VS 二分查找