首 0 尾 1 的 01 串中找一个“01”位置
哪些公司问过
答案要点
- 维护不变式 s[lo]=0、s[hi]=1,初始 lo=0、hi=n-1
- 取中点,s[mid] 为 0 则 lo=mid,否则 hi=mid,区间不断减半
- hi=lo+1 时 lo 即为一个 01 的起始下标
- 时间 O(log n),空间 O(1);不要求串有序,只依赖首 0 尾 1 的条件
- 线性解法:第一个 1 的前一位一定是 0,复杂度 O(n)
易错点
- 误以为必须找第一个 1 才能二分,而无序串无法二分找第一个 1
- 更新时写成 lo=mid+1,破坏 s[lo]=0 的不变式
- 循环终止条件写错导致死循环或越界
面试官常见追问
- 为什么串无序也能二分?
- 如果要找第一个 01 呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。