如何高效识别分层布尔数组中连续true序列的起止索引？

针对你提出的布尔数组约束（最多一段连续True，其余为False），可以通过二分查找变种实现亚线性时间复杂度（O(log n)）且无额外内存的查找方案，具体步骤如下：

1. 确认数组中是否存在True #

通过二分法快速定位是否存在True值：

• 初始化low=0，high=数组长度-1
• 循环判断：
  • 若low > high，说明数组全为False，直接返回无结果
  • 计算中间索引mid=(low+high)//2
  • 若arr[mid]为True，说明存在目标序列，记录pos=mid并跳出循环
  • 若arr[mid]为False，先检查左半区间[low, mid-1]，若左半无True则检查右半区间[mid+1, high]

2. 查找True序列的左边界 #

在[0, pos]范围内用二分法找第一个True的索引：

• 初始化left_low=0，left_high=pos
• 循环直到left_low == left_high：
  • mid=(left_low+left_high)//2
  • 若arr[mid]为True，说明左边界在[left_low, mid]，更新left_high=mid
  • 若arr[mid]为False，说明左边界在[mid+1, left_high]，更新left_low=mid+1
• 最终left_low即为序列起始索引start

3. 查找True序列的右边界 #

在[pos, 数组长度-1]范围内用二分法找最后一个True的索引：

• 初始化right_low=pos，right_high=数组长度-1
• 循环直到right_low == right_high：
  • mid=(right_low+right_high+1)//2（向上取整避免死循环）
  • 若arr[mid]为True，说明右边界在[mid, right_high]，更新right_low=mid
  • 若arr[mid]为False，说明右边界在[right_low, mid-1]，更新right_high=mid-1
• 最终right_low即为序列结束索引end

示例验证 #

以你给出的场景为例：

• 场景00001111110（索引0-10）：找到pos=5（值为1），左边界最终为4，右边界最终为9，对应序列111111
• 场景10000000000：找到pos=0，左边界和右边界均为0
• 场景00000000000：二分后确认无True，返回无结果

该方案仅需几个变量记录索引，无需额外内存，时间复杂度为O(log n)，完全适配数十万级元素的大数组需求。

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