二分查找实现：O(nlogn)预处理+O(logn)查询包含指定点的区间数

看起来你卡在了用二分查找统计包含点的区间数量这一步——你的思路方向对了一半（排序+二分），但具体的实现逻辑走偏了，我来帮你梳理正确的方案：

问题核心 #

你想要的是：给OX轴上的一堆区间，做O(nlogn)的预处理后，能在O(logn)时间内快速查出任意一点被多少个区间包含。你当前的递归二分代码是在找某个和点匹配的区间，这完全不是统计数量的正确姿势，自然没法生效。

正确的预处理+查询思路 #

预处理（O(nlogn)时间） #

我们换个思路：统计包含点x的区间数，等价于左端点≤x的区间总数减去右端点<x的区间总数。基于这个逻辑，预处理步骤如下：

• 遍历所有区间 [L, R]，分别收集两个数组：
  • starts：存所有区间的左端点L
  • ends：存所有区间的右端点+1（也就是R+1，这样我们可以用同样的二分逻辑统计"右端点<x"的数量）
• 对starts和ends分别做升序排序，排序的时间复杂度是O(nlogn)，符合要求。

查询（O(logn)时间） #

对于目标点x：

1. 用二分查找在starts中找到第一个大于x的元素的索引，这个索引值就是左端点≤x的区间总数（因为排序后，前面的所有元素都≤x）
2. 用同样的二分查找在ends中找到第一个大于x的元素的索引，这个值就是右端点+1≤x的区间数，也就是右端点<x的区间数
3. 两者相减，得到的就是包含x的区间数量

这个方法用两次二分查找，每次都是O(logn)，完美满足查询时间要求。

你的代码问题出在哪？ #

你提供的这段递归二分代码，逻辑是在找左端点等于目标点的区间，或者往左找更小的左端点：

# 你给出的不完整代码片段
def algoritmo(inter,i,j,punto):
    if i == j:
        res = -1
    else:
        p = int((i + j) / 2)
        if punto == inter[p][0]:
            res = [inter[p][0],inter[p][1]]
        elif punto <= inter[p][0]:
            res = algoritmo(inter,i,p,punto)
        # 缺少else分支，逻辑也不对

但一个区间包含x的条件是L ≤ x ≤ R，你只盯着左端点找，根本没法统计所有符合条件的区间，自然得不到正确的数量。

完整代码示例 #

用Python的bisect模块（内置二分实现）来写，简洁又高效：

import bisect

def preprocess(intervals):
    starts = []
    ends = []
    for left, right in intervals:
        starts.append(left)
        ends.append(right + 1)  # 存R+1，方便后续统计右端点<x的数量
    starts.sort()
    ends.sort()
    return starts, ends

def count_containing_intervals(starts, ends, x):
    # 左端点<=x的区间数：bisect_right返回第一个大于x的位置，前面的都是<=x的
    left_count = bisect.bisect_right(starts, x)
    # 右端点<x的区间数：即R+1<=x的数量，同样用bisect_right
    right_count = bisect.bisect_right(ends, x)
    return left_count - right_count

# 测试一下
test_intervals = [[1,3], [2,5], [4,7], [6,8]]
starts, ends = preprocess(test_intervals)
print(count_containing_intervals(starts, ends, 5))  # 输出2，因为[2,5]和[4,7]包含5
print(count_containing_intervals(starts, ends, 1))  # 输出1，只有[1,3]包含1
print(count_containing_intervals(starts, ends, 8))  # 输出1，只有[6,8]包含8

复杂度验证 #

• 预处理：两次排序，每次O(nlogn)，总时间O(nlogn)
• 查询：两次二分查找，每次O(logn)，总时间O(logn)

完全符合你要求的时间复杂度。

内容的提问来源于stack exchange，提问作者user9513682