一维布尔数组指定索引的有界最近邻高效查找方案问询

咱们先抓住问题的核心：你的布尔数组是值成组出现的（连续的0或连续的1），这恰恰是优化查找效率的关键——直接遍历数组找最近邻最坏情况是O(n)，但通过预处理把数组转换成区间列表，就能把后续的查找降到O(log k)（k是区间的数量，远小于原数组长度n）。

具体步骤拆解 #

1. 预处理：把原数组转换成区间元组列表

首先一次性遍历原数组，把连续相同值的片段转换成(起始索引, 结束索引, 值)的元组，比如原数组[0,0,0,1,1,0,0,1,1,1]会被处理成：

[(0, 2, 0), (3, 4, 1), (5, 6, 0), (7, 9, 1)]

这个预处理只需要O(n)的时间，但只做一次就行，后续所有查找都基于这个区间列表。

2. 用二分查找定位目标索引所在的区间

因为区间列表是有序且不重叠的，我们可以用二分查找快速找到包含目标索引i的区间。比如要找i=5，很快就能定位到(5,6,0)这个区间。

3. 查找有界最近邻

这里默认你要找的是离i最近的不同值的元素位置（如果是相同值的话，整个区间内都是，直接返回i即可）：

• 如果当前区间不是第一个区间，左边相邻区间的结束索引就是离i最近的左侧不同值的最后位置；
• 如果当前区间不是最后一个区间，右边相邻区间的起始索引就是离i最近的右侧不同值的第一个位置；
• 计算这两个候选位置到i的距离，取最小的那个就是结果；
• 如果整个数组都是同一个值（只有一个区间），那就不存在不同值的最近邻，返回空或做相应处理。

伪代码示例 #

# 预处理数组生成区间列表
def preprocess_bool_array(arr):
    if not arr:
        return []
    intervals = []
    current_val = arr[0]
    start_idx = 0
    for idx in range(1, len(arr)):
        if arr[idx] != current_val:
            intervals.append((start_idx, idx - 1, current_val))
            current_val = arr[idx]
            start_idx = idx
    # 处理最后一段区间
    intervals.append((start_idx, len(arr) - 1, current_val))
    return intervals

# 二分查找目标索引所在的区间
def find_target_interval(intervals, target_idx):
    left, right = 0, len(intervals) - 1
    while left <= right:
        mid = (left + right) // 2
        start, end, _ = intervals[mid]
        if start <= target_idx <= end:
            return mid
        elif target_idx < start:
            right = mid - 1
        else:
            left = mid + 1
    return -1  # 目标索引越界

# 查找最近邻
def find_closest_neighbor(intervals, target_idx):
    interval_pos = find_target_interval(intervals, target_idx)
    if interval_pos == -1:
        return None  # 无效索引
    
    total_intervals = len(intervals)
    candidates = []
    
    # 检查左侧相邻区间
    if interval_pos > 0:
        left_start, left_end, left_val = intervals[interval_pos - 1]
        distance = target_idx - left_end
        candidates.append((distance, left_end, left_val))
    
    # 检查右侧相邻区间
    if interval_pos < total_intervals - 1:
        right_start, right_end, right_val = intervals[interval_pos + 1]
        distance = right_start - target_idx
        candidates.append((distance, right_start, right_val))
    
    if not candidates:
        return None  # 数组全为同一值，无不同值的最近邻
    
    # 按距离排序，取最近的
    candidates.sort(key=lambda x: x[0])
    return (candidates[0][1], candidates[0][2])

为什么这个方法高效？ #

• 预处理仅需一次O(n)操作，后续每次查找都是O(log k)（k是区间数量，因为值成组出现，k远小于n）；
• 对比直接从i向左右遍历的方法（最坏O(n)，哪怕是成组场景，预处理法依然更优），这个方法在大数组场景下优势非常明显；
• 如果是动态数据流（数组不断新增元素），可以动态维护区间列表：每次新增元素时，只需检查是否和最后一个区间的值相同，相同则扩展结束索引，不同则新增区间，维护成本是O(1)每次。

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