如何高效判断指定值在有序区间列表中的所属区间？

问题描述 #

给定有序区间列表（如interval = [-5, -2, 0, 10]，对应三个左开右闭区间：(-5, -2]、(-2, 0]、(0, 10]），需判断给定值属于哪个区间，输出布尔数组（仅对应区间为True，其余为False）。已知待检查值一定处于区间列表的最小值与最大值之间，当前循环遍历的方法在处理长列表时速度较慢，需更高效的实现方案。

最优解决方案：二分查找（内置bisect模块） #

利用Python内置的bisect模块做二分查找，时间复杂度为O(log n)，远优于遍历的O(n)，尤其适合超长区间列表场景。

实现代码 #

import bisect

value = 1
interval = [-5, -2, 0, 10]

# 找到第一个大于value的区间端点索引，减1得到目标区间的下标
target_idx = bisect.bisect_right(interval, value) - 1

# 构造结果数组：仅目标区间设为True
output = [False] * (len(interval) - 1)
output[target_idx] = True

print(output)  # 输出: [False, False, True]

原理说明 #

1. bisect.bisect_right(interval, value)返回值插入区间列表后仍保持有序的位置，这个位置减1正好对应值所在的左开右闭区间下标。比如value=1时，插入位置是3（在0和10之间），减1后得到2，对应第三个区间。
2. 直接构造全False数组，再将目标下标设为True，避免了遍历所有区间的冗余操作。

备选方案：numpy数值加速（适合批量计算场景） #

如果处理大量数值或依赖numpy环境，可使用numpy.digitize实现：

import numpy as np

value = 1
interval = [-5, -2, 0, 10]

# digitize返回区间索引（从1开始），减1转为数组下标
target_idx = np.digitize(value, interval) - 1
output = np.zeros(len(interval)-1, dtype=bool)
output[target_idx] = True

print(output.tolist())  # 输出: [False, False, True]

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