常见查找算法及其实现
哪些公司问过
答案要点
- 顺序查找:O(n),无要求,适合无序或很小的数据
- 二分查找:要求有序,O(log n),注意区间边界和中点溢出
- 插值查找:对分布均匀的有序数据,估算位置,分布不均会退化
- 哈希查找:平均 O(1),需处理冲突,不支持范围查询
- 树结构:O(log n),支持有序遍历和范围查询;无序数据只查一次就线性扫描,多次查找预先建哈希表
易错点
- 对无序数据用二分查找
- 二分的区间边界写错导致死循环
- 说哈希表查找一定是 O(1),不提冲突
面试官常见追问
- 二分查找的实现要注意什么?
- 插值查找什么时候好?
- 哈希和二叉搜索树怎么选?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。