leetcode69 x的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2
示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

思路：二分

别给我说牛顿迭代，你让工作好几年的人写个牛顿迭代？

  

   

    

     

    
    

     

      public class Solution {
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 public int mySqrt(int x) {
     
    
   

    

     

    
    

     
 long left = 0;
     
    
   

    

     

    
    

     
 long right = Integer.MAX_VALUE;
     
    
   

    

     

    
    

     
 while (left < right) {
     
    
   

    

     

    
    

     
 long mid = (left + right + 1) >>> 1;
     
    
   

    

     

    
    

     
 long square = mid * mid;
     
    
   

    

     

    
    

     
 if (square > x) {
     
    
   

    

     

    
    

     

       right = mid - 1;
     
    
   

    

     

    
    

     

       } else {
     
    
   

    

     

    
    

     

       left = mid;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return (int) left;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/103447710