二分查找算术平方根：为什么最后返回right而不是left？

在使用二分查找方法求解整数平方根时，经常会遇到一个问题：循环结束后，究竟应该返回 left 还是 right？本文将详细解释为何返回 right 才是正确的选择。

问题背景

当我们在区间 [left, right] 中寻找目标值的算术平方根时，如果没有找到精确的平方根，循环结束时 left 和 right 会相邻或交叉。此时，如果返回 left，将返回左边界，而它并非我们想要的整数部分的平方根。

为什么返回right？

为了得到正确的整数部分平方根，我们需要返回 right。这是因为：

循环结束条件: 在二分查找的循环中，条件是 left <= right。当循环结束时，意味着 left 已经大于 right，此时 right 指向的是满足条件的最后一个位置。2. 右边界特性: 在不断缩小区间的过程中，right始终指向可能包含目标值的区间的右边界。因此，当循环结束时，right 会停留在不大于目标值的最后一个位置，也就是整数部分的平方根。

代码示例 (Java)

以下是使用二分查找计算整数平方根的修正后的Java代码：javapublic class Solution { public int mySqrt(int x) { if (x == 0) return 0; int left = 1; // 设置左边界为1 int right = x; // 设置右边界为x while (left <= right) { int mid = left + (right - left) / 2; // 取中间值 if (mid == x / mid) { return mid; // 找到平方根，返回中间值 } else if (mid < x / mid) { left = mid + 1; // 平方根在右半部分，调整左边界 } else { right = mid - 1; // 平方根在左半部分，调整右边界 } } return right; // 返回右边界，即整数部分的平方根 }}

总结

在使用二分查找计算整数平方根时，务必牢记循环结束条件和 right 指针的特性，才能确保返回正确的结果。