二分查找的前提是什么?链表能用吗?有哪些应用场景?
哪些公司问过
答案要点
- 前提:有序或判定条件具单调性,能根据中点判断答案在哪一半
- 需要随机访问:数组 O(1) 取中点;链表取中点 O(n),不适合二分
- 有序链式结构可用跳表或平衡 BST 实现对数级查找
- 场景:查找元素与边界、旋转数组、单调函数求根、二分答案
- 细节:区间写法统一,mid=left+(right-left)/2 防溢出,时间 O(log n)
易错点
- 循环条件与边界更新不匹配,导致死循环或漏解
- mid=(left+right)/2 在大整数时可能溢出
- 以为只能用于严格有序数组,忽略二分答案等单调性场景
面试官常见追问
- 左闭右闭和左闭右开写法有什么区别?
- 如何找第一个大于等于 target 的位置?
- 什么是二分答案?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。