查找

线性查找与二分查找，以及二分思想的常见变形。代码继续用 JavaScript。

前置：复杂度基础 · 排序（二分通常要求有序）。

1. 线性查找

从左到右逐个比对，找到就返回下标，否则返回未找到。

• 时间：最好 O(1)，平均/最坏 O(n)
• 空间：O(1)
• 前提：无（无需有序）

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i
  }
  return -1
}

无序数组、链表上的「找一个元素」基本就是这一档。数据已有序时，应优先考虑二分。

2. 二分查找（有序数组）

有序数组上，每次取中点，丢掉一半搜索区间。

• 时间：O(log n)
• 空间：迭代 O(1)，递归 O(log n) 栈
• 前提：单调有序（下面默认升序）

function binarySearch(arr, target) {
  let l = 0
  let r = arr.length - 1
  while (l <= r) {
    const mid = l + ((r - l) >> 1) // 避免 (l+r) 溢出的写法习惯
    if (arr[mid] === target) return mid
    if (arr[mid] < target) l = mid + 1
    else r = mid - 1
  }
  return -1
}

要点：

1. 循环条件用 l <= r（闭区间）时，更新写成 mid ± 1，避免死循环
2. mid 用 l + ((r - l) >> 1) 更稳妥
3. 找到的是「某一个」等于 target 的下标；有重复时不一定是最左或最右

3. 二分边界问题（左边界 / 右边界）

有重复值时，常要：

• 左边界：第一个 >= target 的位置（lower_bound）
• 右边界：第一个 > target 的位置（upper_bound），或最后一个 <= target

模板（左闭右开 [l, r)，找第一个 >= target）：

// 返回第一个 >= target 的下标；若都小于 target，返回 n
function lowerBound(arr, target) {
  let l = 0
  let r = arr.length // 注意：右开，r 可以取到 n
  while (l < r) {
    const mid = l + ((r - l) >> 1)
    if (arr[mid] < target) l = mid + 1
    else r = mid // arr[mid] >= target，答案在左半（含 mid）
  }
  return l
}

// 第一个 > target ≡ lowerBound(target + 1)（整数时）
// 或直接：
function upperBound(arr, target) {
  let l = 0
  let r = arr.length
  while (l < r) {
    const mid = l + ((r - l) >> 1)
    if (arr[mid] <= target) l = mid + 1
    else r = mid
  }
  return l
}

用法示例：

const a = [1, 2, 2, 2, 3]
lowerBound(a, 2)  // 1 —— 第一个 2
upperBound(a, 2)  // 4 —— 第一个大于 2 的位置
// 值为 2 的个数 = upperBound - lowerBound → 3

手写易错点：区间开闭不一致、mid 该归哪边、找不到时返回值约定（下标 / -1 / n）。先固定一种区间约定，整场面试不要混用。

4. 旋转数组中的查找

把有序数组前缀转到末尾，得到「两段有序」：[4,5,6,7,0,1,2]。仍可用二分，关键是：中点落在哪一段有序区间里。

找最小值（旋转点）

function findMinRotated(arr) {
  let l = 0
  let r = arr.length - 1
  while (l < r) {
    const mid = l + ((r - l) >> 1)
    if (arr[mid] > arr[r]) l = mid + 1 // 最小在右半
    else r = mid // 最小在左半（含 mid）
  }
  return arr[l]
}

无重复时 O(log n)；有重复（如 [2,2,2,0,1]）最坏可能退化，需额外处理相等分支。

查找目标值

function searchRotated(arr, target) {
  let l = 0
  let r = arr.length - 1
  while (l <= r) {
    const mid = l + ((r - l) >> 1)
    if (arr[mid] === target) return mid

    // 左半 [l, mid] 有序
    if (arr[l] <= arr[mid]) {
      if (arr[l] <= target && target < arr[mid]) r = mid - 1
      else l = mid + 1
    } else {
      // 右半 [mid, r] 有序
      if (arr[mid] < target && target <= arr[r]) l = mid + 1
      else r = mid - 1
    }
  }
  return -1
}

思路：先判断哪边单调，再看 target 是否落在该单调区间内，从而丢掉另一半。

5. 在答案空间上二分

不一定在下标上二分——只要答案落在单调区间，且能写一个 check(x)：「答案能否 ≤ / ≥ x」，就可以对答案值域二分。

典型：

• 容量 / 速度最小化：check(mid) = 用容量 mid 能否在时限内运完
• 分割数组的最大和最小
• 珂珂吃香蕉、造船等「最小化最大值」

// 框架：在 [lo, hi] 上找满足 check 的最小 mid
function binarySearchAnswer(lo, hi, check) {
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1)
    if (check(mid)) hi = mid // mid 可行，试更小
    else lo = mid + 1 // mid 不可行，必须更大
  }
  return lo
}

// 例：吃完 piles 的最小速度（每小时吃 speed 根，限 h 小时）
function minEatingSpeed(piles, h) {
  const check = (speed) => {
    let hours = 0
    for (const p of piles) hours += Math.ceil(p / speed)
    return hours <= h
  }
  return binarySearchAnswer(1, Math.max(...piles), check)
}

识别信号：要求「最小的最大…」「最大的最小…」，且随答案增大可行性单调变化。

6. 查找相关复杂度小结

场景	典型复杂度	备注
无序线性找	O(n)	无预处理
有序二分	O(log n)	数组随机访问
边界二分	O(log n)	模板要对齐开闭区间
旋转数组查找	O(log n)	有重复时要小心
答案空间二分	O(log R · 单次 check)	R 为答案值域宽度
哈希查找	平均 O(1)	额外空间；最坏退化
平衡 BST	O(log n)	有序动态集合

和排序的关系：先花 O(n log n) 排序，再多次 O(log n) 查询，适合「一次排序、多次查找」。只查一两次且无序时，直接线性扫往往更简单。

---

上一篇：排序 · 下一篇：双指针与滑动窗口