算法图谱

Binary Search

二分查找

查找核心时间 O(log n)空间 O(1)

在有序序列上每次丢掉一半。边界写对，对数时间定位目标。

动画

1
0
2
1
3
2
4
3
5
4
7
5
8
6
9
7

二分查找：在有序数组中找 7

1 / 5

  • 默认

讲解

有序数据的标准查找；也是「答案二分」的模板——能判定就能搜索。

  1. 01维护闭区间 [L, R]，取 mid = (L+R) >> 1。
  2. 02a[mid] == target 则命中。
  3. 03a[mid] < target 则 L = mid + 1，否则 R = mid - 1。
  4. 04循环直到 L > R。变体：找左/右边界时相等也要继续收缩。

易错点

  • 数组必须有序（或满足单调判定）。
  • mid 溢出：用 L + (R-L)//2；死循环通常是边界没排除 mid。

代码

function binarySearch(a, target) {
  let lo = class="text-accent">0, hi = a.length - class="text-accent">1;
  while (lo <= hi) {
    const mid = (lo + hi) >> class="text-accent">1;
    if (a[mid] === target) return mid;
    if (a[mid] < target) lo = mid + class="text-accent">1;
    else hi = mid - class="text-accent">1;
  }
  return -class="text-accent">1;
}

相关课题