查找

二分查找

二分查找的前提是数组已排序。每一轮看中点 mid：

  • 中点正好是目标 → 完成
  • 中点比目标小 → 答案一定在右半，丢掉左半
  • 中点比目标大 → 答案一定在左半，丢掉右半

每一轮区间长度减半，所以最多 ⌈log₂ n⌉ 轮就能定位。

复杂度

  • 时间：O(log n)
  • 空间：O(1)

在动画里看什么

  • L / R：当前活跃区间的左右边界
  • mid：当前检查的位置（深蓝）
  • 灰色：已被丢弃的部分（永远不会再看）
  • 找到时整格变成暖红