布尔数组中从指定索引查找下一个True值的最优方案

我有如下布尔列表：

test_dict = [False, False, True, False, False, True]

我需要一种算法，能从给定位置查找下一个True值。注意：这个起始位置是通过遍历另一个字典得到的，计算时间复杂度时需要把这个外层循环一并考虑。

输入输出示例 #

输入：
test_dict = [False, False, True, False, False, True]
Position = 3
输出：
Next true value is at 5th position

我试过用嵌套for循环，但不确定是不是最优方案，求建议。

补充示例代码 #

test_dict = [False, False, True, False, False, True]
dict_sample = {"1": "2", "11":"3"}
for position, val in dict_sample.items():
    # 这里的position是查找test_dict的起始位置
    # 需要在这里实现查找逻辑

方法1：直接嵌套遍历（基础实现） #

这是最直观的方案，在外层遍历字典的同时，从指定起始位置开始逐个检查test_dict的元素，直到找到第一个True。

代码示例：

test_dict = [False, False, True, False, False, True]
dict_sample = {"1": "2", "11":"3"}

for pos_str, val in dict_sample.items():
    start_pos = int(pos_str)  # 注意字典key是字符串，需转为整数
    next_true_pos = None
    # 从起始位置遍历到列表末尾
    for idx in range(start_pos, len(test_dict)):
        if test_dict[idx]:
            next_true_pos = idx
            break
    if next_true_pos is not None:
        print(f"Next true value is at {next_true_pos}th position")
    else:
        print("No true value found after the given position")

时间复杂度分析 #

假设dict_sample有M个元素，test_dict长度为N。最坏情况下（比如所有查找都找不到True，或True在列表末尾），总时间复杂度为O(M*N)。如果数据规模较大，这个方案效率会偏低。

方法2：预处理True索引（优化方案） #

如果需要多次执行查找操作，先提前提取test_dict中所有True的位置并存储为有序列表，之后每次查找只需在这个列表中做二分查找，能大幅降低时间成本。

步骤： #

1. 预处理：遍历一次test_dict，收集所有True的索引，得到升序列表true_indices。
2. 外层遍历字典时，对每个起始位置，用二分查找找到true_indices中第一个大于起始位置的元素。

代码示例：

import bisect

test_dict = [False, False, True, False, False, True]
dict_sample = {"1": "2", "11":"3"}

# 预处理：收集所有True的索引
true_indices = [idx for idx, val in enumerate(test_dict) if val]

for pos_str, val in dict_sample.items():
    start_pos = int(pos_str)
    # 用bisect_right找到第一个大于start_pos的索引位置
    idx_in_true = bisect.bisect_right(true_indices, start_pos)
    if idx_in_true < len(true_indices):
        next_true_pos = true_indices[idx_in_true]
        print(f"Next true value is at {next_true_pos}th position")
    else:
        print("No true value found after the given position")

时间复杂度分析 #

• 预处理阶段：O(N)，仅需执行一次。
• 单次查找：二分查找时间为O(log K)，其中K是test_dict中True的数量（K≤N）。
• 总时间复杂度：O(N + M*log K)，当M较大时，该方案比嵌套遍历高效得多。

方案选择建议 #

• 若数据规模小或查找次数少，直接嵌套遍历即可，代码简单易读。
• 若需频繁查找或数据规模大，优先选择预处理+二分查找的方案，性能提升显著。

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