Leetcode基础刷题之PHP解析(二分查找之69. Sqrt(x))

2 0 1 9 -5 -10   星 期五     开 始 吧

上 一 题 链 接 Leetcode基础刷题之 PHP 解析(二分查找之33，35)

题 目 描 述

计算给定数的平方根，因为返回的类型是整形，不保留小数点，这里还是使用二分查找求。

题 目 分 析

可以这样利用二分搜索每次算一下选定值的平方，和给定值进行比较，进行对应情况的处理.

/**
     * @param Integer $x
     * @return Integer
     */
    function mySqrt($x) {
        $l=0;
        $r=$x;
        while($l<=$r){
            $middle=$l+(($r-$l)>>1);
            $res=$middle*$middle;
            if($x==$res) return $middle;
            else if($res<$x) $l=$middle+1;
            else $r=$middle-1;
        }
        return $r;
   }   

换一种写法

/**
     * @param Integer $x
     * @return Integer
     */
    function mySqrt($x) {
        if($x==0) return 0;
        $l=1;
        $r=floor($x/2)+1;
        while($l<=$r){
            $middle=$l+(($r-$l)>>1);
            if($middle<=$x/$middle && $x/($middle+1) <$middle+1){
                return $middle;
            }
            if($middle>$x/$middle){
                $r=$middle-1;
            }else{
                  $l=$middle+1;
            }
        }  
    }

这道题看了一下还可以用牛顿迭代法完成，可以自己去完成下。

Github整理地址: https://github.com/wuqinqiang/leetcode-php