高效统计列表中上下界内元素数量的O(nlogn)方法（Python实现）

核心思路 #

针对大型无序列表的多组区间查询，最优方案是先对列表排序（时间复杂度O(nlogn)），之后每组查询通过二分查找快速定位区间边界，单次查询仅需O(logn)时间。这种方式比每次查询都遍历列表（单次O(n)）高效得多，尤其在查询组数较多时优势显著。

具体逻辑：

1. 对原列表排序，重复元素会自然集中，为二分查找提供有序基础。
2. 针对每组查询的上下界[low, high]，用二分查找定位两个关键索引：
   • 第一个大于等于low的元素索引（记为left_idx）
   • 第一个大于high的元素索引（记为right_idx）
3. 区间内元素数量即为right_idx - left_idx，结果天然包含边界值。

Python实现 #

Python标准库的bisect模块封装了成熟的二分查找方法，直接调用bisect_left和bisect_right即可完成定位：

import bisect

def count_in_range():
    # 读取输入
    n = int(input())
    nums = list(map(int, input().split()))
    # 排序列表，O(nlogn)时间复杂度
    nums.sort()
    query_count = int(input())
    for _ in range(query_count):
        low, high = map(int, input().split())
        # 定位第一个>=low的元素索引
        left_pos = bisect.bisect_left(nums, low)
        # 定位第一个>high的元素索引
        right_pos = bisect.bisect_right(nums, high)
        print(right_pos - left_pos)

if __name__ == "__main__":
    count_in_range()

代码细节解释 #

• bisect.bisect_left(nums, low)：返回将low插入列表后仍保持有序的第一个位置，对应原列表中第一个大于等于low的元素索引；若所有元素均小于low，则返回列表长度。
• bisect.bisect_right(nums, high)：返回将high插入列表后仍保持有序的第一个位置，对应原列表中第一个大于high的元素索引；若所有元素均小于等于high，则返回列表长度。
• 两者的差值恰好是[low, high]区间内的元素总数，自动包含边界值。

示例验证 #

用题目给出的输入测试：
输入：

5
2 4 98 3 100
4
99 101
1 5
100 100
2 2

排序后的列表为[2, 3, 4, 98, 100]：

• 查询99-101：bisect_left返回4，bisect_right返回5，5-4=1，输出1。
• 查询1-5：bisect_left返回0，bisect_right返回3，3-0=3，输出3。
• 查询100-100：bisect_left返回4，bisect_right返回5，5-4=1，输出1。
• 查询2-2：bisect_left返回0，bisect_right返回1，1-0=1，输出1。
  完全匹配示例输出。

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