面试算法题：有序列表查找所有匹配目标值的下标 要求O(log n)复杂度

你当前的实现存在一个不符合题目要求的问题：当目标值在数组中出现的次数为n量级时（比如整个数组都是目标值），找到匹配下标后向左右遍历的步骤时间复杂度为O(n)，整体不满足O(logn)的要求，同时还存在未找到目标值时传入布尔值作为索引的报错风险。

优化的核心是用两次二分查找，分别定位第一个等于目标值的左边界和最后一个等于目标值的右边界，拿到两个边界后直接生成下标范围即可，整体时间复杂度严格为O(logn)，实现也更简洁。

以下是可直接运行的实现代码：

data = [2,3,5,6,8,9,12,12,12,14,17,19,22,25,27,28,33,37]
target = 12

def get_target_indices(data, target):
    n = len(data)
    # 查找第一个等于target的左边界
    left, right = 0, n-1
    first_idx = -1
    while left <= right:
        mid = (left + right) // 2
        if data[mid] == target:
            first_idx = mid
            right = mid - 1 # 继续向左查找更早的匹配项
        elif data[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    if first_idx == -1: # 无匹配直接返回空
        return []
    # 查找最后一个等于target的右边界
    left, right = first_idx, n-1
    last_idx = first_idx
    while left <= right:
        mid = (left + right) // 2
        if data[mid] == target:
            last_idx = mid
            left = mid + 1 # 继续向右查找更晚的匹配项
        elif data[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    # 直接生成连续下标列表
    return list(range(first_idx, last_idx + 1))

print(get_target_indices(data, target))

运行输出为：[6, 7, 8]，和原有实现的结果一致。

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