LC704
二分查找
二分查找 · 标准可视化:二分查找在升序数组 [-1,0,3,5,9,12] 中查找 target=9 的下标。
时间 O(log n)空间 O(1)
题目1 / 8
题目与输入建立输入、目标与算法心智
有序数组,答案若存在必在 [lo, hi] 内
正在加载算法场景...
当前发生了什么
在升序数组 [-1,0,3,5,9,12] 中查找 target=9 的下标。
机器状态
候选区间下界 lo、上界 hi、中点 mid。
为什么正确
维护候选区间 [lo,hi];每步取 mid 比较,丢弃一定不含答案的一半。
不变量
答案若存在,一定落在当前候选区间 [lo, hi] 内。
面试怎么说
数组有序,我维护候选区间 [lo,hi],每步取 mid:相等即返回,a[mid] 偏小则 lo=mid+1,偏大则 hi=mid-1;每步砍半,O(log n)。
人类输入
在升序数组 [-1,0,3,5,9,12] 中查找 target=9 的下标。
机制
维护候选区间 [lo,hi];每步取 mid 比较,丢弃一定不含答案的一半。
机器状态
候选区间下界 lo、上界 hi、中点 mid。
可观察结果
在下标 4 处找到 9。
不变量
- · 答案若存在,一定落在当前候选区间 [lo, hi] 内。
常见误区
- · mid 比较后要写 mid±1,否则区间不缩小会死循环。
迁移练习
- · LC35 搜索插入位置
- · LC33 旋转有序数组搜索
面试怎么答
数组有序,我维护候选区间 [lo,hi],每步取 mid:相等即返回,a[mid] 偏小则 lo=mid+1,偏大则 hi=mid-1;每步砍半,O(log n)。