algorithm - 如何找到已排序列表的子集的边界？

Question

我有以下困境:我有一个字符串列表，我想找到以某个前缀开头的字符串集。列表已排序，所以天真的解决方案是这样的:

对集合的前缀进行二分查找，当找到以该前缀开头的元素时，线性向上遍历，直到到达子集的顶部。

然而，这是在线性时间内运行的，我想知道是否有人可以建议一种更有效的方法来做到这一点。

Answer 1

对顶部进行二分查找，对底部进行二分查找。一旦找到第一个命中点，您就知道顶部在该点上方，底部在该点下方(或者在这两种情况下都在该点)。一旦你有了顶部和底部，你就有了解决方案。