二分查找专题
二分查找的思路人人都会，写对的却不多：边界、终止条件、重复元素时的取左 / 取右，都要有固定模板。写错几乎都不是算法问题，而是区间开闭与循环条件没配套。
一、什么时候能用二分
「有序」只是表象，真正的条件是存在单调性：能根据中间点的值判断答案在左半边还是右半边，从而排除一半。所以数组有序能用，答案空间单调（比如「速度越快越能在规定时间内完成」）也能用——后者就是二分答案。
只要满足「每次能排除一半」，就能二分，不管数据本身是不是排好序的。一个判断技巧：问自己「如果中间点满足条件，左半边能不能整体排除」——能，就有单调性，可以二分。
二分的代价也值得算一遍：每次折半，所以是 O(log n)——一百万条的有序数据最多比 20 次。但它的前提是单调性：数组有序只是单调的一种，二分答案那类题里单调的是「判定函数」，不是数据本身。
二、两种区间写法
最容易写错的是区间开闭不一致导致的死循环。给两条能直接套的模板，关键点是 mid 的计算与边界更新方式要配套。
mid 写成 left + ((right - left) >> 1) 而不是 (left + right) / 2，是为了防止 left + right 在数值极大时溢出（在要求严格的语言里这是硬规则，也是好习惯）——同时右移等效向下取整，行为可预期。
// 找左边界（第一个满足条件的）：右开区间 [left, right)
function lowerBound(nums, target) {
let left = 0, right = nums.length
while (left < right) {
const mid = left + ((right - left) >> 1)
if (nums[mid] >= target) right = mid // 等于时也收缩右边界
else left = mid + 1
}
return left
}
// 找右边界（最后一个满足条件的）：命中时收缩左边界
function upperBound(nums, target) {
let left = 0, right = nums.length
while (left < right) {
const mid = left + ((right - left) >> 1)
if (nums[mid] <= target) left = mid + 1 // 等于时收缩左边界
else right = mid
}
return left
}
模板要连区间一起记：while (left < right) 配右开区间，right = mid 不 -1；若用 while (left <= right) 闭区间，则 right = mid - 1。混用就会死循环或漏答案。
三、重复值取左还是取右
等于 target 时要不要继续收缩，决定了返回的是第一个还是最后一个。lowerBound 里 nums[mid] >= target 时收右边界，最终停在第一个 >= target 的位置（即第一个等于 target 处）；upperBound 里 <= target 时收左边界，最终停在最后一个 = target 的下一个。这一步直接决定答案语义，是重复元素题的核心。
等于时收缩哪一侧，决定返回的是第一个还是最后一个
中点取法也有坑，两个大数相加可能溢出：
// >> 是 32 位运算，下标很大时会被截断；left + ((right - left) >> 1) 能绕开这个陷阱
const mid = (left + right) >> 1
// 对：用「起点 + 半程」的写法，永不丢精度
const mid = left + ((right - left) >> 1)
四、死循环与边界
三个高频坑：
- 溢出：
(left + right) / 2在极大数下溢出，用left + ((right - left) >> 1)。 - 开闭不一致：
while (left <= right)却写right = mid（不-1），区间没变小，死循环。 - 退出后不检查：循环结束时
left可能越界（等于nums.length），直接当索引用会错，要先确认是否真的找到了。
// 死循环的写法：闭区间却没把 right 真正缩小
while (left <= right) {
const mid = (left + right) >> 1
if (nums[mid] === target) return mid
else if (nums[mid] < target) left = mid + 1
else right = mid // ❌ 应为 right = mid - 1，否则 left==right 时卡死
}
退出时边界可能越界，用之前先检查是否真的命中
五、对答案本身做二分
把「求最优解」转成「判定可行性」：先猜一个值，写个 check(x) 判断 x 是否可行，再在答案空间上二分。典型如「分割数组的最大值最小」「运输能力」「天数安排」——这些题直接求最优很难，但「给定上限能不能满足」是单调的（上限越大越容易满足），于是对上限二分。二分答案的搜索区间通常取「最小可能」到「最大可能」（如分割数组的上限是总和、下限是最大元素），这样边界天然正确，不用额外处理越界。
// 二分答案：在 [1, maxSum] 上找「子数组和最大值」的最小可能
function splitArray(nums, m) {
let left = Math.max(...nums), right = nums.reduce((a, b) => a + b, 0)
while (left < right) {
const mid = left + ((right - left) >> 1)
if (canSplit(nums, m, mid)) right = mid // mid 可行，尝试更小
else left = mid + 1
}
return left
}
关键是证明 check 的单调性：上限放宽后，原来能分割的依然能分割。有了单调性，二分才成立。
模板靠背一定会错，写个随机对照跑一遍就踏实了：
for (let i = 0; i < 2000; i++) {
const n = (Math.random() * 50 + 1) | 0
const a = Array.from({ length: n }, () => (Math.random() * 20) | 0).sort((x, y) => x - y)
const target = a[(Math.random() * n) | 0]
const idx = lowerBound(a, target)
if (a[idx] !== target) throw new Error('模板不对')
if (idx > 0 && a[idx - 1] >= target) throw new Error('不是最左位置')
}
console.log('2000 组随机用例通过')
六、背模板写不对
二分不只用在排序数组上，只要能构造出单调判定就能用，「二分答案」是典型例子。
循环条件用 < 还是 <= 也不是无所谓——它与区间的开闭绑定，混用会死循环或漏答案。
循环结束更不能直接用 mid，退出时边界可能已经越界，必须再检查一次是否真的命中。
模板要连区间一起记：while (left < right) 配右开区间，right = mid 不减一；换成闭区间的写法，配套的收缩方式也要跟着变。
边界写法容易在差一错误上翻车，OI Wiki 二分 给了几种标准模板，对照着写会稳。