69.md

2019-05-09 吴亲库里 库里的深夜食堂

:pencil2:题目描述

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

:pencil2:题目实例

​

---

:pencil2:题目分析

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

---

:pencil2:最终实现代码

    /**
        * @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;
      }   

---

:pencil2:换一种写法

/**
   * @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;
          }
      }  
  }

---

:pencil2:还可以使用牛顿迭代法完成

联系

​