数据结构与算法 · 单选题 · 第 59 题
计算机基础面试八股 · 第 59 题
使用二分查找的前提条件是?
- A序列中的元素必须两两互不相同
- B序列有序,并且支持按下标随机访问
- C序列的长度必须是 2 的整数次幂
- D数据必须用单链表来存储
答案
B B. 序列有序,并且支持按下标随机访问
解析
二分查找每次比较中间元素来排除一半区间,依赖有序性;而取中间元素要求 O(1) 随机访问,单链表做不到。元素可以重复,这时可以查找第一个或最后一个等于目标的位置。长度没有要求,注意写对边界条件,中点用 lo + (hi - lo) / 2 防止溢出。