面试题库 › C++ / 后端 › 二分查找第一个大于或大于等于目标值的元素

二分查找第一个大于或大于等于目标值的元素

难度 ★★☆在 3 场真实面经中被问到 方向:C++ / 后端考点:查找算法

哪些公司问过

腾讯1字节跳动1阿里云1

常见岗位:Java 后端、iOS、C/C++ 软件开发

答案要点

  1. 数组必须有序,无序时先排序 O(n log n),之后每次二分 O(log n)
  2. 左闭右开写法:right 初始为 n,a[mid]>=target 时 right=mid,否则 left=mid+1
  3. 循环结束 left 即第一个满足条件的位置,left==n 表示不存在
  4. “第一个大于”只需把条件改为 a[mid]>target,字符串用字典序比较
  5. “最后一个小于 x”等于“第一个大于等于 x”的下标减一,对应 lower_bound/upper_bound

易错点

面试官常见追问

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

相关面试题