醉丶春风的Blog

使用二分法求一个数的平方根

假如我们有一个数字8, 现在使用代码来求它的平方根, 我们预期的结果是4, 那在代码中是怎么处理的呢

此处我们使用二分查找法, 模拟过程如下

1. 第1次计算: 0-8的中间值=4, 4*4=16, 16大于8, 此时我们的查找范围缩小到了0-4, 继续
2. 第2次运算: 0-4的中间值=2, 2*2=4, 4小于8, 此时我们的查找范围缩小到了2-4, 继续
3. 第3次运算: 2-4的中间值=3, 3*3=9, 9大于8, 此时我们的查找范围缩小到了2-3, 继续
4. 第4次运算: 2-3的中间值=2.5, 2.5*2.5=6.25, 6.25小于8, 此时我们的查找范围缩小到了2.5-3, 继续
5. ......

代码实现

function mySqrt($number) {
    // 小于等于0的数字不计算
    if ($number <= 0) {
        return 0;
    }
    $min = 0;
    $max = $number;
    // 计循环次数
    $i = 0;
    // 结束循环条件写在了循环体里面
    while (true) {
        $i++;
        $mid = ($min + $max) / 2;
        $square = $mid * $mid;

        // 误差小于 0.000000001 即退出循环
        if (abs($number - $square) < 0.000000001) {
            break;
        }
        if ($square < $number) {
            $min = $mid;
        } elseif ($square > $number) {
            $max = $mid;
        } else {
            break;
        }
    }
    $mid = round($mid, 9);
    // 打印信息
    echo sprintf('数字: %s, 计算了 %d 次, 结果为: %s , 调用系统函数计算结果为: %s<br>', $number, $i, $mid, sqrt($number));

    return $mid;
}

调用测试

mySqrt(16);
mySqrt(3);
mySqrt(8);
mySqrt(999999999);

输出为:

数字: 16, 计算了 2 次, 结果为: 4 , 调用系统函数计算结果为: 4
数字: 3, 计算了 33 次, 结果为: 1.732050808 , 调用系统函数计算结果为: 1.7320508075689
数字: 8, 计算了 31 次, 结果为: 2.828427125 , 调用系统函数计算结果为: 2.8284271247462
数字: 999999999, 计算了 68 次, 结果为: 31622.776585872 , 调用系统函数计算结果为: 31622.776585872