使用二进制搜索查找多个条目 [英] Finding multiple entries with binary search

问题描述

我使用标准的二进制搜索来快速返回排序列表中的单个对象（关于可排序属性）。

I use standard binary search to quickly return a single object in a sorted list (with respect to a sortable property).

现在，我需要修改搜索，以便返回 ALL 匹配列表条目。我应该如何最好地做到这一点？

Now I need to modify the search so that ALL matching list entries are returned. How should I best do this?

推荐答案

好吧，随着列表的排序，所有您感兴趣的条目都是连续。这意味着您需要查找与找到的项目相同的第一项，并从二进制搜索生成的索引中向后看。和最后一项相同。

Well, as the list is sorted, all the entries you are interested in are contiguous. This means you need to find the first item equal to the found item, looking backwards from the index which was produced by the binary search. And the same about last item.

您可以简单地从找到的索引中倒退，但是如果存在a，则求解的速度可能与O（n）一样慢。等于找到的物品很多。因此，您最好使用指数搜索：当您找到更多相等项时，将跳转次数增加一倍。这样，您的整个搜索仍然是O（log n）。

You can simply go backwards from the found index, but this way the solution may be as slow as O(n) if there are a lot of items equal to the found one. So you should better use exponential search: double your jumps as you find more equal items. This way your whole search is still O(log n).

这篇关于使用二进制搜索查找多个条目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！