leetcode 69. Sqrt(x)

Seawolf

1. Implement int sqrt(int x).
   
2. 
   
3. Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
   
4. 
   
5. Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
   
6. 
   
7. Example 1:
   
8. 
   
9. Input: 4
   
10. Output: 2
    
11. Example 2:
    
12. 
    
13. Input: 8
    
14. Output: 2
    
15. Explanation: The square root of 8 is 2.82842..., and since
    
16.              the decimal part is truncated, 2 is returned.

复制代码

1. class Solution {
   
2.     public int mySqrt(int x) {
   
3.         long start = 0;
   
4.         long mid = 0;
   
5.         long end = x;
   
6.         
   
7.         while(start+ 1 < end){
   
8.             
   
9.             mid = start + (end - start)/2;
   
10.             
    
11.             if(mid * mid == x) return (int)mid;
    
12.             else if(mid * mid < x) start = mid;
    
13.             else end = mid;
    
14.         }
    
15.         
    
16.         if(end * end == x) return (int)end;
    
17.         
    
18.         return (int)start;
    
19.     }
    
20. }

复制代码