二分查找：
循环不变量、防溢出中点与边界跨越

区间开闭决定一切：何为“循环不变量”？

给定一个升序整型数组 nums 和一个目标值 target。写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

写二分查找的第一步，永远不是敲 while，而是在心中定义好你的查找区间类型。定义一旦确定，后续每一步的代码都必须严格维护这个定义（即“循环不变量”）：

双指针夹逼推演，观察搜索空间折半。

推演中观察 L（左界）、R（右界）与 M（探针中点）。每一步比对后，被排除的半边数组将被置为半透明灰阶，展现搜索规模以几何级数对数骤减的过程。

三个关键细节：防整型溢出、循环条件与边界步进

1. 01

   为什么不能写 (left + right) / 2？

   在 C/C++ 等强类型语言中，int 通常为 32 位带符号整数（上限约 $2.14 \times 10^9$）。当 left 和 right 都很大（例如在海量数据检索或二分答案时），两数相加 left + right 会直接整型溢出翻转为负数，导致 mid 成为负数并引发内存段错误！必须写成 left + (right - left) / 2，先减后加，数学等价且在数学上永远不会发生上溢。

2. 02

   为什么闭区间必须是 left <= right？

   如果是左闭右开 [left, right)，那么当 left == right 时区间 [left, left) 为空，条件应该写 left < right。但如果使用的是双闭区间 [left, right]，当 left == right 时，该位置上的元素还没有被核验过！例如单元素数组 [5] 找 5，初始 left = 0, right = 0。如果误写为 left < right，循环根本不会进入，直接错误返回 -1。因此双闭区间必须写 <=。

3. 03

   必须加一减一：left = mid + 1 与 right = mid - 1

   许多初学者偷懒写 left = mid 或 right = mid。由于整数除法是向下取整，当区间只剩两个元素时（例如 left = 0, right = 1），mid = 0 + 0 / 2 = 0。若此时 nums[0] < target 且你执行 left = mid，left 依然为 0！区间范围完全没有缩小，程序陷入无限死循环。既然 nums[mid] 已经确认不是 target，必须坚决将其移出下一轮考察范围。

真实 C 语言实现节选

选自 CSP 练习记录中已通过评测的源码。纯粹的逻辑，严格的防溢出与边界控制。

int search(int *nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1; // 1. 采用双闭区间 [left, right]
    int mid;

    while (left <= right) {   // 2. 当 left == right 时区间依然有效
        mid = left + (right - left) / 2; // 3. 防整型加法溢出写法
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;   // 4. 严格跳过 mid，防止死循环
        } else {
            right = mid - 1;  // 4. 严格跳过 mid，防止死循环
        }
    }
    return -1; // 搜索区间为空，目标不存在
}

对数复杂度的威力与极限