二分查找

二分查找 = 在单调性上做边界定位（lower/upper）与答案搜索（parametric search）

#algorithm #concept #growing #binary-search #array

[!info] related notes 算法面试题型 MOC

二分查找（Binary Search）

二分的核心不是“在有序数组里找数”，而是：

找到一个单调的判定函数 P(x)（或把问题改写成单调判定）
用对数次判定定位边界；总耗时还要乘上每次判定的成本

常见两类：

边界二分：在有序数组上定位 lower_bound / upper_bound
答案二分：在答案空间上二分（parametric search / binary search on answer）

1) 边界二分（lower_bound / upper_bound）

定义（数组 nums 非递减）：

lower_bound(target)：最小的下标 i，使得 nums[i] >= target（不存在则返回 n）
upper_bound(target)：最小的下标 i，使得 nums[i] > target（不存在则返回 n）

推荐只熟练掌握 1 套区间写法（下面用 左闭右开 [l, r)），其余写法只是等价变形。

推荐模板：左闭右开 [l, r)

// lowerBound: first index i with nums[i] >= target
// if not found, returns n
function lowerBound(nums, target) {
  let l = 0, r = nums.length; // [l, r)
  while (l < r) {
    const mid = Math.floor((l + r) / 2);
    if (nums[mid] >= target) r = mid;
    else l = mid + 1;
  }
  return l;
}

// upperBound: first index i with nums[i] > target
function upperBound(nums, target) {
  let l = 0, r = nums.length; // [l, r)
  while (l < r) {
    const mid = Math.floor((l + r) / 2);
    if (nums[mid] > target) r = mid;
    else l = mid + 1;
  }
  return l;
}

// searchRange: [first, last] of target, or [-1, -1]
function searchRange(nums, target) {
  const first = lowerBound(nums, target);
  const lastExclusive = upperBound(nums, target);
  if (first === nums.length || first === lastExclusive) return [-1, -1];
  return [first, lastExclusive - 1];
}

典型题型（LeetCode 热题 100 优先）：

LeetCode 34 - Find First and Last Position of Element in Sorted Array（边界：lower/upper 组合）
LeetCode 35 - Search Insert Position（lower_bound 直接应用）

等价写法（了解即可）

闭区间 [l, r] 版本通常用 while (l <= r)，但更新规则也要一起改变；不能只替换循环条件。下方另给出开区间版本，不是闭区间代码。

// 开区间 (l, r)
function lowerBoundOpen(nums, target) {
  let l = -1, r = nums.length;
  while (l + 1 < r) {
    const mid = Math.floor((l + r) / 2);
    if (nums[mid] >= target) r = mid;
    else l = mid;
  }
  return r;
}

左闭右开 [l, r)：推荐上面的模板（本质上也是“边界收缩”）。

2) 答案二分（Binary Search on Answer / Parametric Search）

当你能写出一个单调判定 check(x) 时，就可以在答案空间二分。

典型形式（求最小可行解）：

check(x) == true 表示 x 足够大/足够强/满足条件
check(x) 随 x 单调：x 越大越容易满足（或反过来，视问题定义）

求最小满足条件的 x

// 前提：整数 lo <= hi，check 为 false→true，且 check(hi) 为 true
// 在 [lo, hi] 上找第一个 true
function firstTrue(lo, hi, check) {
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (check(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

典型题型（LeetCode 热题 100 优先）：

LeetCode 410 - Split Array Largest Sum（标准答案二分：最小可行上限）

求最大满足条件的 x

// 前提：整数 lo <= hi，check 为 true→false，且 check(lo) 为 true
// 在 [lo, hi] 上找最后一个 true
function lastTrue(lo, hi, check) {
  while (lo < hi) {
    const mid = Math.floor((lo + hi + 1) / 2); // +1 防止死循环
    if (check(mid)) lo = mid;
    else hi = mid - 1;
  }
  return lo;
}

这两个示例不返回“无可行解”的独立状态：调用前要证明存在可行端点，或先检测无解并按契约返回。端点和中点运算还需在语言的安全整数范围内。

常见分类（还需证明判定单调，不能仅凭优化目标套用）：

最小化某个值（minimize max / minimize cost）
最大化某个值（maximize min / maximize score）
第 K 小/大（常用：二分值域 + 计数 check）

2.1 最小化最大值（minimize the maximum）

特征：给定一个阈值 x，能否做到“所有约束的最大值 <= x”。

写法：

check(x)：是否存在一种方案，使得“最大代价/最大差值/最大时间/最大容量”等不超过 x
单调性：x 越大越容易满足（true 区间在右侧）

// 伪代码：把问题变成 check(x) 是否可行
// return firstTrue(lo, hi, check)
function check(x) {
  // greedily / dp / counting ...
  // return true if feasible under max <= x
}

典型题型（LeetCode 热题 100 优先）：

LeetCode 410 - Split Array Largest Sum（最小化“最大分组和”）

2.2 最大化最小值（maximize the minimum）

特征：想让“最小值尽可能大”（如最小间距、最小得分、最小收益）。

写法：

check(x)：是否能做到“最小值 >= x”（也就是至少能达到 x）
单调性：x 越大越难满足（true 区间在左侧）
模板：用 lastTrue(lo, hi, check)

// check(x): can we achieve min >= x ?
function check(x) {
  // greedy / counting ...
}

// ans = lastTrue(lo, hi, check)

最小间距类题常采用该模式，但寻找重复数不属于“最大化最小值”：它使用 count(<= mid) > mid 的 false→true 判定，找的是第一个超额值域。

2.3 第 K 小/大：二分“值域” + 计数 check

当你能在 O(n) 或 O(n log n) 内回答：

“<= mid 的元素有多少？”
“满足条件的 pair/triple 有多少？”

就可以二分答案 mid。

常见：

有序数组里第 K 小：count(<= mid) 用 upperBound
矩阵/双指针计数：count(<= mid)
距离/差值类：count(<= mid)（常见用双指针）

// 找最小 x，使得 count(<= x) >= k
function kthSmallestByValueRange(lo, hi, k, countLE) {
  return firstTrue(lo, hi, (x) => countLE(x) >= k);
}

典型题：有序矩阵中第 K 小的元素。值域计数与旋转数组中“哪半段有序”的判断是不同证明，不能混成同一 predicate。

例题

使结果不超过阈值的最小除数

3) 常见坑与自检（每条配 1 道题）

单调性写反：先定义 check(x) 的 true/false 含义，再判断 x 变大时更容易 true 还是更容易 false
- 典型题型：LeetCode 410（limit 越大越容易可行）
边界选不全：lo/hi 必须覆盖所有可能答案；不确定就先用“保守边界”再收紧
- 典型题型：LeetCode 410（上界/下界如何取，直接决定对不对）
死循环：求最大值用 mid = floor((l + r + 1) / 2)；每次循环必须严格缩小区间
- 典型题型：LeetCode 35（边界二分最容易写成不收敛）
结果校验：返回的是“边界下标/边界答案”，不是 mid；必要时用一次检查验证
- 典型题型：LeetCode 34（需要校验是否真的存在 target）

对应例题笔记：

信息参考

二分查找红蓝染色法【基础算法精讲 04】_哔哩哔哩_bilibili