我使用标准的二进制搜索 快速返回排序列表 中的单个对象(关于可排序属性)。
现在我需要修改搜索以便返回 ALL 匹配的列表条目。我应该如何最好地做到这一点?
最佳答案
好吧,由于列表已排序,您感兴趣的所有条目都是连续的。这意味着您需要找到等于找到的项目的第一个项目,从二分查找产生的索引向后看。最后一项也是如此。
您可以简单地从找到的索引开始倒退,但如果有很多项与找到的项相同,那么解决方案可能会像 O(n) 一样慢。所以你应该更好地使用指数搜索:当你找到更多相同的项目时,你的跳跃加倍。这样你的整个搜索仍然是 O(log n)。
关于algorithm - 使用二进制搜索查找多个条目,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12144802/