algorithm_BinarySearch

pepper 2025-12-20

algorithm

这篇博客介绍了二分查找法则。

4.2 求开方

69. Sqrt(x) (Easy)

题目描述 给定一个非负整数，求它的开方，结果向下取整。

输入输出样例 输入一个整数，输出一个整数。

Input: 8
Output: 2

解释：8 的开方结果是，向下取整即是 2。

自己撰写的版本 1 的代码如下。

int l=1, r=m, res=0;
// int mid = l + (r-l)/2;
// 1. 如果input m=0；
if(m==0) return res=0;
// 2. 其他正常情况下，注意每一次都要择半查找，直到l>r
while(l<r && r>l)
{
    mid = l + (r-l)/2; // 每一轮都要更新一下
    if(mid * mid == m)
    {
        return mid;
    }else if(mid * mid > m )
    {
        r = mid;
    }else{
        l = mid;
    }
}
// 这个时候都不满足条件的时候
return l;

分析其存在的问题：

乘法溢出（计算风险）

问题所在：在代码中使用了 if(mid _ mid == m)。如果 m 是 int 的最大值，在二分查找过程中 mid 可能会取到较大值。例如 mid = 100,000 时，mid _ mid 会达到 10,000,000,000，这远超 int 的范围。结果： mid * mid 会溢出变成一个乱码数字（可能是负数）。

修改建议：使用 sqrt = a / mid 的方式，比较 sqrt 是否和和 mid 相等，如果 sqrt > mid，就说明 mid 还需要小一点，往左区间。如果 sqrt < mid，则就说明 mid 可以再大一点点。

修改后的代码如下：

int mySqrt(int a){
    if(a==0) return a;
    int sqrt,mid,l=1,r=a;
    while(l<=r){
        mid = l + (r-l)/2 ;
        sqrt = a / mid;
        if(mid == sqrt){
            return mid;
        }else if(mid > sqrt){ // 因为全文都在赋数值修改左右边界，如果mid大于sqrt了，就说明，mid得再分一点给sqrt，所以要在左区域查找；
            r = mid-1;
        }else{
            l = mid+1;
        }
    }
    return r;
}

详细记录补充：

1. 中点计算的加法溢出 (Arithmetic Overflow)

分析原因：如果使用 $mid = (l + r) / 2$，当 l 和 r 都很大时（例如接近 int 的最大值 $2^{31}-1$），它们的和会瞬间超过 int 的表示范围，导致结果变成负数，从而使 mid 计算错误。
解决方法：使用 $mid = l + (r - l) / 2$。这种写法在数学上等价，但在计算机运算中，由于先做了减法，保证了数值始终在 [l, r] 范围内波动，不会溢出。

不是所有情况都会溢出。是否溢出取决于实际数值与所使用的编程语言中该数据类型的最大上限之间的关系。

以下是详细的分类讨论：

什么时候会发生溢出？

在 C、C++、Java、Go 等静态类型语言中，int 类型通常是 32 位有符号整数。

安全情况： 如果，那么 (l + r) / 2 是完全安全的。例如在处理只有 10 万个元素的数组时，索引绝对不会溢出。
溢出情况： 如果和都很大，比如，。
它们的数学和应该是。
但这超过了 int 的上限，计算机会发生“环绕”（Wrap-around），结果会变成一个负数。
负数除以 2 还是负数，这会导致你的 mid 变成一个毫无意义的负索引，程序随后就会报错（数组越界）。

为什么 l + (r - l) / 2 永远安全？

我们可以从数学和内存两个角度来看：

数学等式： $l + \frac{r - l}{2} = \frac{2l + r - l}{2} = \frac{l + r}{2}$ 。它们在数学上是一模一样的。
内存安全： 在计算 r - l 时，因为，所以结果一定是一个非负数且小于。在计算 l + 偏移量 时，因为最终结果是 mid，而 mid 始终位于和之间，只要本身没有溢出，整个计算过程中的**任何中间变量都不会超过 **。

不同编程语言的表现不同

Python 3：不会溢出 Python 3 的 int 是动态精度的（长整型），它会自动根据数值大小分配内存。只要你的电脑内存够大，Python 可以处理无限大的整数。所以在 Python 中写 mid = (l + r) // 2 是安全的。

C++ / Java：必须小心 在这些语言中，如果你处理的数据规模可能达到级别（例如 LeetCode 的某些大数题目），就必须使用 l + (r - l) / 2 或者将变量声明为 long long / long。

在 C++/Java 等语言中： 永远推荐写 mid = l + (r - l) / 2;。这是一种职业素养，能避免在处理大规模数据时出现难以排查的 Bug。
另一种黑科技写法（仅限 C++/Java）： mid = (l + r) >> 1; 这种写法在处理正数时和除以 2 等价，但它在溢出成负数时依然会出错。 更高级的写法： mid = (l + r) >>> 1;（Java 中的无符号右移），它可以完美处理溢出。