01｜二分基础（边界与不变量）（知识笔记）
对应课程：lessons/01-complexity-and-binary-search/01-binary-search-basics.md
二分的本质
二分不是“写个 while”，而是维护一个不变量：
- 答案一定落在你维护的区间里
- 每次用
mid排除一半
最常见的两类目标：
- 找最小可行（first true）
- 找最大可行（last true）
你必须先说清楚的三件事
check(x)的意义是什么？check(x)是否单调？方向是什么？- 返回值语义：我到底返回“第一个满足”还是“最后一个满足”？
低风险写法（强烈推荐固定写法，不要每次即兴）
找最小 x 使 check(x)=true（false...true）
- 思维：缩小右边界直到刚好可行
- 写法要点：
mid = l + (r-l)/2- 若
check(mid)为真：r = mid（保留 mid） - 否则：
l = mid + 1
找最大 x 使 check(x)=true（true...false）
- 思维：扩张左边界直到刚好不可行前一位
- 写法要点：
mid = l + (r-l+1)/2（偏右）- 若
check(mid)为真：l = mid - 否则：
r = mid - 1
常见坑（重点看）
mid不偏右导致死循环（last true 场景）check不是单调的（本质错误）- 溢出：当 l,r 到 1e18，
l+r会溢出 - 边界：全 false / 全 true 的情况
自检（提交前 20 秒）
- [ ] 我能画出
check的真假分界吗？ - [ ] 我能手推 3 次循环检查 l,r 是否收敛吗？
- [ ] 极端：答案在最左/最右是否正确？
个人坑位
- （例）我经常把
r=mid-1写到 first true 模板里