求O(log n)时间复杂度的分组数字区间查找解决方案

问题描述 #

给定连续分组的数字数组：

arr = [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 8, 8, 8, 8, 8, 4, 4, 4, 4]

需求是找出每个数字对应的索引区间（同数字连续排列），预期输出：

1: (0,5)
2: (6,10)
3: (11,14)
8: (15,19)
4: (20,23)

要求实现时间复杂度为O(log n)，且需尽量减少数组元素访问次数（场景为ETL管道，访问元素需下载100GB文件）。

解决方案思路 #

利用二分搜索定位每个连续分组的左右边界，结合分组的连续性减少重复搜索：

• 从数组起始位置开始，先获取当前分组的目标数字
• 用二分搜索找到该数字的最后出现位置（右边界）
• 记录当前数字的区间(当前左边界, 右边界)
• 将下一个分组的左边界设为右边界 + 1，重复上述步骤直到遍历完数组

这种方式下，每个分组的边界查找仅需O(log k)时间（k为当前分组长度），总时间复杂度等价于O(log n)，且大幅减少了数组元素的访问次数。

代码实现（Python） #

def find_right_bound(arr, target, left, right):
    res = -1
    while left <= right:
        mid = (left + right) // 2
        mid_val = arr[mid]
        if mid_val == target:
            res = mid
            left = mid + 1  # 继续向右找最后一个匹配项
        elif mid_val > target:
            right = mid - 1
        else:
            left = mid + 1
    return res

arr = [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 8, 8, 8, 8, 8, 4, 4, 4, 4]
n = len(arr)
current_left = 0

while current_left < n:
    target = arr[current_left]
    current_right = find_right_bound(arr, target, current_left, n-1)
    print(f"{target}: ({current_left},{current_right})")
    current_left = current_right + 1

输出验证 #

运行上述代码后，输出与预期完全一致：

1: (0,5)
2: (6,10)
3: (11,14)
8: (15,19)
4: (20,23)

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