二分查找：每次排除一半

一句话理解

二分查找利用“序列已经有序”这个信息，每次比较中点后排除一半候选区间。

逐步观察

选择目标值，然后逐步执行。变淡的格子已经被逻辑排除；青色格子是当前中点。

复杂度

如果序列长度是 $n$，最多经过约 $\log_2 n$ 次比较：

function binarySearch(values: number[], target: number) {
  let left = 0;
  let right = values.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (values[mid] === target) return mid;
    if (values[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

易错点

边界更新必须排除已经检查过的中点，否则可能陷入无限循环。