二分边界 / First True

数学 / 逻辑形态

维护闭区间 [lo,hi] 且已知答案存在其中；mid 为 True 时保留 mid 并令 hi=mid，否则排除 mid 令 lo=mid+1，终止于 lo=hi。

识别信号

要找首次、最左、至少、lower bound。
候选位置的谓词从某点起永久为真。
重复元素使“任意命中”不够。
答案本身已知存在于初始化区间，或能放置真哨兵。

容易误判的相似信号

Signal	Why it is different
任意精确命中	不要求边界时普通二分更直观。
非单调谓词	T/F 多次交替时，丢掉一半没有逻辑依据。

核心不变量

第一个 True 始终位于 [lo,hi]；hi 一侧是保留的可行候选，lo 左侧已证为 False。

状态、转移与处理顺序

Item	Definition
State	lo、hi、mid 和单调 predicate；模板假设区间内至少一个 True。
Transition	predicate(mid) 为 True：hi=mid；否则 lo=mid+1。
Frontier / order	仍可能成为转折点的闭区间；mid 为 True 时不能做 hi=mid-1，因为 mid 可能就是答案。

Python 骨架

def first_true(lo, hi, predicate):
    # Precondition: predicate(hi) is True.
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if predicate(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

正确性思路

若 predicate(mid) 真，单调性只说明答案不在 mid 右边，mid 本身仍可能是首真，故保留 [lo,mid]。
若为假，mid 及左侧都不可能是首真，安全保留 [mid+1,hi]。
区间严格缩小到单点；不变量与存在性保证该点就是首真。

复杂度

Time	Space	Parameters
O(log N) 次谓词调用	O(1) 外加谓词空间	N=hi-lo+1；若 predicate 成本为 C，总时间 O(C log N)。

边界条件

lo 初始就为 True 时应返回 lo。
只有 hi 为 True 时仍会收敛到 hi。
若可能没有 True，需要真哨兵或返回前验证。
整数域之外的实数二分需改用迭代次数/误差终止。

错误模式

Pattern	Why it fails / fix
True 时 hi=mid-1	会丢掉可能的第一个 True。
while lo<=hi 混搭 hi=mid	区间语义不一致，容易死循环。
未验证单调性	局部样例看似可用，不代表谓词只有一次转折。

选择与排除规则

先写出 F F | T T 的示意，再决定更新。
能证明 predicate(hi)=True 时用收敛单点模板。
last True 可反转谓词或使用对称的上取整 mid 模板。

Relation	Template	Boundary
控制结构母版	答案空间二分	can(x) 就是 first-True 谓词。
加速谓词	前缀和 / 区间聚合	边界判断需频繁查询区间聚合。
组合查询	Sparse Table 静态 RMQ	用 O(1) RMQ 检验并寻找边界
optimization	子序列 DP	某些单序列递增子序列长度可用 tails + lower_bound。

原创微型例子

环节	内容
Result	收敛到首个 True 的索引 3。
Setup	谓词在索引 0..6 上为 F,F,F,T,T,T,T。
Trace	检查 3 得 T，保留 [0,3]；检查 1 得 F，保留 [2,3]；检查 2 得 F。

Recall prompts

为什么 True 时必须保留 mid？
模板对 predicate(hi) 有什么前置条件？
last True 为什么常用上取整 mid？

二分边界 / First True

数学 / 逻辑形态

识别信号

容易误判的相似信号

核心不变量

状态、转移与处理顺序

Python 骨架

正确性思路

复杂度

边界条件

错误模式

选择与排除规则

相关模板

原创微型例子

Recall prompts

我的补充