algorithm - 搜索间隔列表的时间复杂度

Question

让a是一个间隔 [a.start, a.end] , 其中a.start和 a.end是实数使得 0 <= a.start < a.end <= 1 .

两个这样的间隔 a和 b 相交 如果a.start < b.start < a.end或者 b.start <= a.start < b.end

让As是非相交区间的排序列表 a_0, a_1, ..., a_n这样 a_i不相交 a_j和 a_i.start < a_j.start对于 i < j

给定区间 b ，确定As中的第一个区间和最后一个区间那b相交(或找不到交点)。即:如果可能，找到 i和 j这样 b 与 a_i 相交和 a_j但不是 a_{i-1}或 a_{j+1}

---

我已经用修改后的二分查找法解决了这个问题(最坏情况下为 O(n))，所以我的直觉是这是一个 lg(n) 问题，但我不知道我是否有最好的算法.

Answer 1

因为你有一个非相交区间的排序列表，你知道每个区间在下一个区间开始之前结束，你也可以把这个列表看成是区间起点的排序列表，或者区间终点的排序列表.

我认为你可以在一个排序的区间端点列表上使用二分查找来找到最小的区间端点，它在 O(log n) 最坏情况下至少和 b.start 一样大，这是第一个与 b 相交的区间(如果有任何区间与 b 相交)。同理，最后一个与b相交的区间最大起点不大于b.end，若有区间与b相交。

要找到至少与目标一样大的最小点，请查看可能解决方案范围中间的点(按可能解决方案的数量，而不是按位置)。如果该点至少与目标一样大，则可能解的范围从该点向左延伸，并包括该点。如果该点至少与目标一样大，则可能的解决方案范围会从该点之后向右延伸。在任何一种情况下，您都将可能解决方案的数量减少了大约一半，因此最坏情况为 O(log n)。