LeetCode二分查找中pivot++/--超时、pivot+1/-1可通过的原因是什么？

核心问题本质 #

超时是错误使用后置自增/自减运算符导致死循环，和二分查找的区间收敛逻辑冲突，完全达不到要求的O(log n)时间复杂度。

具体原因拆解 #

1. 后置自增/自减的运算规则 #

Java 中后置pivot++、pivot--的执行顺序为：

• 先返回变量的原始值，参与当前行的赋值运算
• 再对变量本身执行+1/-1操作
  而代码中每轮循环开头都会重新执行pivot = left+(right-left)/2覆盖pivot的值，所以后置自增/自减对pivot的修改完全无效，相当于边界赋值逻辑完全不符合预期。

2. 错误代码的实际执行逻辑 #

未通过的代码：

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int pivot = 0;
        while (left <= right) {
            pivot = left+(right-left)/2;
            if (nums[pivot] == target) return pivot;
            if (nums[pivot] > target) right = pivot--;
            else left = pivot++;
        }
        return -1; 
    }
}

其中的边界赋值实际生效逻辑为：

• 当nums[pivot] > target时，预期把右边界设为pivot-1，但实际执行的是right = pivot
• 当nums[pivot] < target时，预期把左边界设为pivot+1，但实际执行的是left = pivot

3. 死循环触发场景 #

当搜索区间缩小到左右边界相邻时，比如left=2、right=3，此时计算得到pivot=2 + (3-2)/2 = 2：
如果此时nums[pivot] < target，按照错误逻辑left会被赋值为2，和之前的左边界完全一致，下一轮循环的left和right仍然是2和3，pivot计算结果永远是2，循环永远无法退出，最终触发Time Limit Exceeded报错。

4. 正确代码的逻辑验证 #

可正常通过的代码：

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int pivot = 0;
        while (left <= right) {
            pivot = left+(right-left)/2;
            if (nums[pivot] == target) return pivot;
            if (nums[pivot] > target) right = pivot-1;
            else left = pivot+1;
        }
        return -1;   
    }
}

这里直接使用pivot+1、pivot-1计算结果赋值给边界，每轮循环的搜索区间都会严格缩小，保证了O(log n)的时间复杂度，不会出现死循环。

内容的提问来源于stack exchange，提问作者Allen Jiang