Python中如何高效判断某个数字是否属于给定区间列表中的某一区间

解决方案 #

方案1：简单遍历（适合区间数量少、单次查询的场景） #

如果你的区间总数少于100个，且只需要做几次查询，直接遍历是性价比最高的写法，Python标准语法就能实现，无需额外依赖：

a = [[167772352, 167772415], [167772160, 167772223], [167772288, 167772351], [167772224, 167772255]]
b = 167772241

# 返回匹配的区间原索引（Python从0开始计数，第4个区间对应索引3）
match_idx = next((i for i, (low, high) in enumerate(a) if low <= b <= high), None)
print(match_idx) # 输出3

说明：如果没有匹配的区间，match_idx会返回None

方案2：二分查找（最优性能，适合区间数量多、多次查询的场景） #

用Python自带的bisect标准库就能实现，无需安装第三方依赖，预处理完成后每次查询时间复杂度只有O(log n)，远优于遍历的O(n)：

import bisect

a = [[167772352, 167772415], [167772160, 167772223], [167772288, 167772351], [167772224, 167772255]]
b = 167772241

# 预处理：保存原索引的同时按区间左边界排序
sorted_with_origin_idx = sorted(enumerate(a), key=lambda x: x[1][0])
left_edges = [item[1][0] for item in sorted_with_origin_idx]
right_edges = [item[1][1] for item in sorted_with_origin_idx]

# 查询逻辑
pos = bisect.bisect_right(left_edges, b) - 1
if pos >=0 and right_edges[pos] >= b:
    match_origin_idx = sorted_with_origin_idx[pos][0]
else:
    match_origin_idx = None

print(match_origin_idx) # 输出3

说明：预处理只需要做一次，后续不管查询多少次都只用跑二分逻辑即可，区间数量越大性能优势越明显。

方案3：区间树（适合复杂区间操作场景） #

如果你的需求包含大量区间增删、重叠查询等复杂操作，可以用第三方库intervaltree，安装命令pip install intervaltree，使用示例：

from intervaltree import Interval, IntervalTree

a = [[167772352, 167772415], [167772160, 167772223], [167772288, 167772351], [167772224, 167772255]]
b = 167772241

# 构建区间树（intervaltree默认左闭右开，所以右边界要+1适配我们的左闭右闭规则）
tree = IntervalTree()
for origin_idx, (low, high) in enumerate(a):
    tree.add(Interval(low, high+1, data=origin_idx))

# 查询
matches = tree[b]
if matches:
    match_origin_idx = next(iter(matches)).data
else:
    match_origin_idx = None

print(match_origin_idx) # 输出3

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