在Or-tools模型中如何高效返回首个为True的布尔值关联的KnownValue

我的模型列表中包含这类数据：Or-tools布尔值与KnownValue相关联。
已知规则为：当某个布尔值变为True时，其下方所有布尔值也会变为True。
我希望返回首个值为1（即True）的布尔值对应的KnownValue，示例中需返回2。
请问如何实现才能获得更优性能？

1. 线性遍历（基础优化） #

利用数据的规则特性——一旦某个位置布尔值为True，后续所有值全为True，不需要遍历整个列表：

• 从列表头部开始逐个检查布尔值
• 找到第一个为True的元素时，立即返回其KnownValue并终止遍历
• 时间复杂度：O(k)，k为第一个True元素的位置，最佳情况O(1)，最坏情况O(n)

示例伪代码：

def find_first_true_known_value(model_list):
    for item in model_list:
        if item.boolean_var.Value() == 1:  # Or-tools获取布尔变量值的方法
            return item.known_value
    return None  # 所有值均为False的情况

2. 二分查找（最优性能） #

因为数据是前缀全False、后缀全True的有序结构，用二分查找可以将时间复杂度降到O(logn)：

• 初始化左右指针left=0，right=len(model_list)-1
• 取中间位置mid，检查布尔值：
  • 若为True，说明第一个True在左半部分（含mid），将right=mid
  • 若为False，说明第一个True在右半部分，将left=mid+1
• 当left == right时，该位置即为第一个True的位置，返回对应KnownValue

示例伪代码：

def find_first_true_known_value_binary(model_list):
    left = 0
    right = len(model_list) - 1
    result_index = -1
    while left <= right:
        mid = (left + right) // 2
        if model_list[mid].boolean_var.Value() == 1:
            result_index = mid
            right = mid - 1  # 继续向左寻找更早的True
        else:
            left = mid + 1
    return model_list[result_index].known_value if result_index != -1 else None

3. Or-tools层面的额外优化 #

• 缓存变量值：若需多次查询，可一次性将所有布尔变量的值缓存到列表中，避免重复调用Value()方法
• 构建时绑定索引：在模型列表构建阶段，同步记录每个KnownValue对应的布尔变量位置，减少后续查找的关联开销

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