面试题库 › 嵌入式 › 首 0 尾 1 的 01 串中找一个“01”位置

首 0 尾 1 的 01 串中找一个“01”位置

难度 ★★☆在 1 场真实面经中被问到 方向:嵌入式考点:查找算法

哪些公司问过

元戎启行1

常见岗位:C/C++ 软件开发

答案要点

  1. 维护不变式 s[lo]=0、s[hi]=1,初始 lo=0、hi=n-1
  2. 取中点,s[mid] 为 0 则 lo=mid,否则 hi=mid,区间不断减半
  3. hi=lo+1 时 lo 即为一个 01 的起始下标
  4. 时间 O(log n),空间 O(1);不要求串有序,只依赖首 0 尾 1 的条件
  5. 线性解法:第一个 1 的前一位一定是 0,复杂度 O(n)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题