算法阅读笔记

Binary Search

Binary search finds a target in a sorted search space by repeatedly discarding half of the remaining range.

类型算法分类Search深度初级典型复杂度O(log n)

简短面试回答

先从这个心智模型开始

Binary search finds a target in a sorted search space by repeatedly discarding half of the remaining range.

简单解释

它如何工作，不堆砌不必要的术语

Compare target with the middle element.

If target is smaller, continue in the left half; if larger, continue in the right half.

执行过程

把算法读成一连串决策

Set left and right bounds.

Compute mid without leaving the range.

Move exactly one bound after each comparison until found or left > right.

记住一个小例子

Searching 23 in [3, 8, 12, 23, 31, 44] checks the middle, then keeps only the half where 23 can still exist.

易读的 JavaScript 实现JavaScript

function binarySearch(items, target) {
  let left = 0;
  let right = items.length - 1;

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

如何阅读这段代码

不要死记语法。跟踪每一行中发生变化的状态，并把它与上面描述的不变量联系起来。

复杂度

O(log n)

Do not quote this complexity mechanically. Ask which operation or input dimension it describes, then derive the cost from the loops, recursion depth, data-structure operations and any preprocessing assumptions.

何时使用

适用场景

Match the algorithm to the structure and preprocessing state of the data.

常见错误

通常哪里会出错

Using it on unsorted data.
Off-by-one errors and infinite loops.
Not defining whether boundaries are inclusive or half-open.

面试中如何解释

专业回答结构

Say the invariant: if the target exists, it is inside the current search interval. Then explain how each comparison preserves that invariant while halving the interval.

问题→核心思路→不变量 / 状态→Big-O→权衡

快速面试检查

What problem does Binary Search solve?

Binary search finds a target in a sorted search space by repeatedly discarding half of the remaining range.

关于复杂度应该提到什么？

Its typical cost here is O(log n), but a complete answer should connect that cost to the representation, input constraints and the dominant operations.

最常见的错误是什么？

Using it on unsorted data.

继续阅读Sorted arraysLower/upper boundBinary search on answer

function binarySearch(items, target) { let left = 0; let right = items.length - 1; while (left <= right) { const mid = left + Math.floor((right - left) / 2); if (items[mid] === target) return mid; if (items[mid] < target) left = mid + 1; else right = mid - 1; } return -1; }