递归二分查找求平方根代码处理大数时出错，求修复方案

你的代码在处理极大数值时失败，核心原因是整数溢出和变量类型不匹配，以下是具体问题分析和修复方案：

问题点分析 #

• int类型容量不足：原代码中start、end、sqrt（传递给num的变量）都使用int类型，但输入参数N是long long。当N超过int的最大值（通常为2^31-1）时，end = N会直接触发整数溢出，导致搜索边界完全错误。
• 乘法运算溢出：mid*mid的计算可能超出long long的范围（例如mid接近1e9时，mid*mid达到1e18，刚好是long long的上限；若mid更大，会溢出为负数，导致判断逻辑失效）。

修复后的代码 #

递归版本 #

#include <bits/stdc++.h> 

long long binarySearch(long long N, long long start, long long end, long long& num){
    if(start > end){
        return num;
    }
    
    long long mid = start + (end - start)/2;
    // 用除法替代乘法，避免溢出，同时处理mid=0的特殊情况
    if(mid == 0){
        num = 0;
        start = mid + 1;
    } else if(N / mid >= mid){
        num = mid;
        start = mid + 1;
    } else {
        end = mid - 1;
    }

    binarySearch(N, start, end, num);
    return num;
}


long long sqrtN(long long N)
{
    long long start = 0;
    long long end = N;
    long long sqrt_val = 0;

    binarySearch(N, start, end, sqrt_val);
    return sqrt_val;
}

可选：迭代版本（避免递归栈溢出） #

如果处理的数值极大（如1e18），递归深度约为60层，虽通常不会触发栈溢出，但迭代版本更稳妥：

long long sqrtN(long long N)
{
    long long start = 0;
    long long end = N;
    long long result = 0;
    
    while(start <= end){
        long long mid = start + (end - start)/2;
        if(mid == 0){
            result = 0;
            start = mid + 1;
        } else if(N / mid >= mid){
            result = mid;
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return result;
}

修复说明 #

1. 统一变量类型：将所有涉及边界和结果的变量改为long long，确保能容纳极大数值，避免初始化边界时的溢出。
2. 替换乘法判断：用N / mid >= mid代替mid*mid <= N，彻底规避乘法溢出风险；增加mid == 0的判断，防止除以0的错误。
3. 迭代优化：递归改迭代可以避免极端情况下的栈溢出问题，同时保持二分查找的时间复杂度O(logN)。

内容的提问来源于stack exchange，提问作者Niteesh Kulhari