从二分查找面试题延伸：查找下界、旋转数组、山峰数组，二分变体一张图看懂

图 1：本文封面，下界查找四轮收缩命中「第一个 7」。

同批的真题复盘逐行排查了一份「找最后一个等于目标值」的错误二分代码，那份代码这里不再展开。这篇把镜头拉远：二分查找不是一段要背的代码，而是一个有三个自由度的模板族。自由度想清楚，「找第一个」「找最后一个」「插入位置」「旋转数组」「山峰数组」全是同一台机器拧不同的螺丝。

三个自由度：区间、循环条件、收缩方向。

自由度一，区间开闭。闭区间 [lo, hi] 初始化 hi = n − 1，区间里全是待查候选；半开区间 [lo, hi) 初始化 hi = n，hi 永远指向「第一个被排除的位置」。两种都能写对，混用必错。

自由度二，循环条件。lo <= hi 表示「区间只剩一个元素也要进去查」，退出时 lo > hi，答案由边界变量带出来；lo < hi 表示「剩一个就停」，退出时 lo == hi，答案往往就是 lo 本身（可能需要补一次判断）。

自由度三，收缩方向，最关键的一个。每轮比较后要砍掉一半，规则只有一句：不可能含答案的那一侧用 mid ± 1 把 mid 排除掉，可能含答案的那一侧用 mid 把 mid 保留下来——保留侧的 mid 还能再当候选，排除侧的 mid 已经审完了。

为什么有的写法必须向上取整。

「左边界保留 mid」（lo = mid）配合 lo < hi 的循环条件时藏着终止性陷阱：区间只剩两个元素（hi = lo + 1）时，向下取整的 mid 就是 lo，lo = mid 等于没动，死循环。所以这类模板必须配 mid = (lo + hi + 1) / 2 向上取整，保证 lo 每轮至少前进一格。同批真题里那段错误代码，正是死在这一格上。

六个变体，一套坐标系。

下面用 JavaScript 给出六个常考变体（统一用闭区间 + lo <= hi 这组自由度），全部经过实测：断言样例加 4.5 万组随机数据暴力对拍，零不一致。

// 1 标准查找：命中返回下标，否则 -1
function binarySearch(a, t) {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (a[mid] === t) return mid;
    if (a[mid] < t) lo = mid + 1; else hi = mid - 1;
  }
  return -1;
}
// 2 下界：第一个 >= t 的下标（全小于 t 时返回 n）
function lowerBound(a, t) {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (a[mid] >= t) hi = mid - 1; else lo = mid + 1;
  }
  return lo;
}
// 3 最后一个 <= t 的下标（全大于 t 时返回 -1）
function lastLE(a, t) {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (a[mid] <= t) lo = mid + 1; else hi = mid - 1;
  }
  return hi;
}

注意 lowerBound 与 lastLE 的镜像关系：一个「大于等于就往左挤」，答案从 lo 带出；一个「小于等于就往右挤」，答案从 hi 带出。在此之上，「第一个等于 t」是先查下界再验证 a[lo] == t，「最后一个等于 t」是 lastLE 后验证 a[hi] == t；插入位置（第一个大于 t 的地方）只需把 lowerBound 里的 >= 换成 >。三个变体不需要新模板，只是判定条件换了符号。

图 2：三个自由度与六个变体的对照，新题照着坐标系拧螺丝。

两个「看起来不能二分」的变体。

旋转数组（升序数组整体搬了一段到前面，如 [4,5,6,7,0,1,2]）的关键观察：任意一刀砍下去，两半里至少有一半仍然有序。先判断哪半有序，再看目标落在不在有序半的范围里——在就收缩进这半，不在就去另一半，每轮照样砍掉一半。

山峰数组（严格先升后降）更直接：比较 a[mid] 与 a[mid + 1]，上升段说明峰顶在右边（lo = mid + 1），下降段说明峰顶是 mid 或在左边（hi = mid，保留候选），用 lo < hi 模板，退出时 lo 即峰顶。

这两个变体说明同一件事：二分的本质不是「数组有序」，而是「每轮能确定地排除一半」。单调性只是最常用的那把刀，任何能把搜索空间对半砍的判定条件都能二分。

拿到新题怎么套。

三步走：先写清答案的定义——是「命中某个值」，还是「第一个满足某性质的位置」；再选收缩方向——哪一侧一定没有答案；最后由收缩方向反推循环条件与取整方向。写完别急着交，用三组用例砸一遍：目标不存在、目标在边界、区间只剩两个元素，二分代码的错误九成藏在这三处。你写二分是背模板派还是现场推导派？被哪个变体坑得最惨？评论区聊聊。