二分查找：循环不变量与边界
二分查找是每个程序员的入门第一课，但也是写错率最高的模板之一：while 条件用 < 还是 <=？right 更新成 mid 还是 mid - 1？靠背答案迟早翻车。这篇文章用"循环不变量"一个思想，把所有边界问题一次理顺。
二分的前提条件
二分查找有两个硬性前提，缺一个就不能用：
- 有序性：数据必须按目标属性有序（升序或降序）。有序保证了"排除一半"的正确性——中点与目标比较后，目标必然只可能落在剩下的一半里。
- 可随机访问：必须能 O(1) 拿到任意位置的元素。数组满足，链表不满足（链表找中点本身就要 O(n)，二分失去意义）。
一个容易忽略的推论：二分不只用于"数组里找数"。只要问题能定义出一个"单调的判定函数"——比如 69 求平方根里"mid² ≤ x 是否成立"、35 搜索插入位置里"nums[mid] < target 是否成立"——就能对解空间二分。这叫"二分答案"，是后面大量题目的进阶套路。
两套区间写法：选一套，贯彻到底
二分的所有纠结都来自一个定义问题：当前搜索区间是 [left, right] 还是 [left, right)。两种定义都正确，但区间定义必须和三处代码保持自洽：while 循环条件、right 的初始值、区间收缩时 right 的更新值。
写法一：闭区间 [left, right]
循环不变量：target 一定在 [left, right] 内（若存在）。
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1; // 闭区间 [0, n-1]
while (left <= right) { // 区间非空才继续：left==right 时 [x,x] 仍有效
int mid = (left + right) >>> 1;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1; // mid 已排除，新区间 [mid+1, right]
} else {
right = mid - 1; // mid 已排除，新区间 [left, mid-1]
}
}
return -1;
}自洽性逐条验证：
- 区间是闭的 →
left == right时区间[x, x]还有一个元素，必须用<=；用<会漏查一个元素。 nums[mid]已比较过 → 它必须被排除出区间 →left跳到mid + 1、right退到mid - 1，两个分支都是"舍弃 mid"。
写法二：半开区间 [left, right)
循环不变量：target 一定在 [left, right) 内（若存在）。
public int search(int[] nums, int target) {
int left = 0, right = nums.length; // 半开区间 [0, n)
while (left < right) { // 区间非空才继续：left==right 意味着空区间
int mid = (left + right) >>> 1;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1; // 新区间 [mid+1, right)
} else {
right = mid; // 新区间 [left, mid)，mid 被排除但 right 本身不在区间内
}
}
return -1;
}自洽性逐条验证：
- 区间右端开 →
left == right（如[3, 3)）就是空区间，必须用<。 - 右分支收缩时写成
right = mid：因为right这个位置本来就不属于区间，把边界挪到 mid（含）不会把 mid 漏掉，同时 mid 也被排除了。这是半开区间最反直觉的一行，靠不变量推而不是靠背。
两套写法对照表
| 要素 | 闭区间 [l, r] |
半开区间 [l, r) |
|---|---|---|
| right 初始值 | nums.length - 1 |
nums.length |
| while 条件 | left <= right |
left < right |
| 右收缩 | right = mid - 1 |
right = mid |
| 左收缩 | left = mid + 1 |
left = mid + 1 |
| 循环结束含义 | 区间为空（交错） | 区间为空（重合） |
建议主用闭区间写法（更符合直觉），半开区间做到能看懂、能判断别人代码的对错。考试式的错误示范是：while 用 <，right 更新却写 mid - 1——区间定义前后矛盾，某些用例必然漏解或死循环。
mid 计算的防溢出写法
朴素写法 mid = (left + right) / 2 有一个隐患：left 和 right 都是 int，相加可能超过 Integer.MAX_VALUE，溢出成负数，导致数组越界异常。LeetCode 极端用例下真的会踩到。
int mid = left + (right - left) / 2; // 写法 A：先减后加，永不溢出
int mid = (left + right) >>> 1; // 写法 B：无符号右移，等价且更简洁两种都行。>>> 是无符号右移：即使和溢出到负数，最高位被当作数值位右移，结果仍然正确。注意 >>（带符号右移）不具备这个性质。Java 里推荐 >>> 1。
查找边界：34 的左右边界二分
704 这类"找到就返回"是二分的入门形态。进阶形态是 LeetCode 34：找到 target 在数组中的起始和结束位置，要求 O(logn)。关键区别：数组里有重复元素，不能找到就停，要把查找"推"到最左或最右。
思路：写一个"找第一个 ≥ x 的下标"的函数（俗称 lowerBound），它本身就是二分答案：
// 返回第一个 >= x 的下标；不存在则返回 nums.length
private int lowerBound(int[] nums, int x) {
int left = 0, right = nums.length - 1;
int ans = nums.length; // 记录候选答案
while (left <= right) {
int mid = (left + right) >>> 1;
if (nums[mid] >= x) {
ans = mid; // mid 可能是答案，先记下
right = mid - 1; // 继续往左找更靠前的
} else {
left = mid + 1;
}
}
return ans;
}
public int[] searchRange(int[] nums, int target) {
int start = lowerBound(nums, target); // 第一个 >= target
if (start == nums.length || nums[start] != target) {
return new int[]{-1, -1}; // target 不存在
}
int end = lowerBound(nums, target + 1) - 1; // 第一个 >= target+1 的前一位
return new int[]{start, end};
}两个要点：
- 找右边界不用单独写模板：
lowerBound(target + 1) - 1一步到位，少背一个容易混淆的版本。 - 与 704 的区别在于：命中后不 return，而是记录答案继续收缩，把"找到一个解"升级为"找最靠边的解"。这个"记录 + 收缩"的手法是所有边界二分的通用骨架。
复杂度与易错点
每轮循环区间至少缩小一半，n 个元素最多 log₂n + 1 轮：时间 O(logn)，空间 O(1)。这也是"有序数据优先想二分"的理由——O(n) 遍历和 O(logn) 二分在 n = 10⁹ 时是天壤之别。
易错点清单：
- while 条件与 right 更新不自洽（最常见，用不变量自查）。
(left + right) / 2溢出，未用>>> 1或left + (right - left) / 2。- 数组无序就上二分——先确认前提。
- 34 类边界题在"target 不存在"分支漏判：lowerBound 返回 n 或
nums[start] != target都要处理。 - 收缩时写成
left = mid（而不是mid + 1），在两元素区间可能死循环。
对应 LeetCode 题目
| 题号 | 题名 | 一句话考点 |
|---|---|---|
| 704 | 二分查找 | 两套区间写法的基础模板 |
| 35 | 搜索插入位置 | lowerBound 的直接应用，target 不存在时返回插入点 |
| 34 | 在排序数组中查找元素的第一个和最后一个位置 | 左右边界二分，记录 + 收缩手法 |
| 69 | x 的平方根 | 二分答案：对"mid² ≤ x"的单调判定函数二分 |