含重复元素的有序数组查询首现索引 如何规避O(n)提升搜索速度

针对有序数组的查找场景，使用左边界二分查找可以将单次查询时间复杂度从O(n)降至O(log n)，同时配合输入输出的批量处理优化，可以轻松支撑百万级的数据量。

优化核心逻辑 #

• 原线性遍历的问题：当N和k都达到1e6上限时，最坏需要执行1e12次比较，完全无法在合理时间内完成运算。
• 左边界二分查找适配性：题目要求查找目标值首次出现的位置，刚好是左边界二分的经典适用场景，每次查询仅需要最多20次左右的比较（log₂(1e6)≈20）。
• 输入输出优化：Python原生的input()逐行读取和print()逐次输出在大数据量下性能极差，改为一次性读取所有输入、一次性输出所有结果可以大幅降低IO开销。

完整优化代码 #

import sys

def left_bound_search(arr: list[int], target: int) -> int:
    low = 0
    high = len(arr)
    # 左边界二分逻辑
    while low < high:
        mid = (low + high) // 2
        if arr[mid] >= target:
            high = mid
        else:
            low = mid + 1
    # 校验是否存在目标值
    if low < len(arr) and arr[low] == target:
        return low + 1 # 转换为1开头的索引
    return 0

def main():
    # 一次性读取所有输入，拆分转成整数列表
    all_data = list(map(int, sys.stdin.read().split()))
    ptr = 0
    n = all_data[ptr]
    k = all_data[ptr+1]
    ptr +=2
    arr = all_data[ptr:ptr+n]
    ptr +=n
    queries = all_data[ptr:ptr+k]
    # 批量计算所有查询结果
    res = [str(left_bound_search(arr, t)) for t in queries]
    # 一次性输出
    print(' '.join(res))

if __name__ == "__main__":
    main()

效果验证 #

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

输入：
10 4
4 8 9 9 9 9 18 28 32 100
4 9 28 32

代码输出结果为1 3 8 9，和示例输出完全一致。

性能对比 #

原线性实现面对1e6长度的数组和1e6次查询，最坏情况需要数小时才能跑完，优化后的实现整体时间复杂度为O(N + k log N)，在Python中也可以在几秒内完成计算。

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