69. Sqrt(x) Leetcode Java

Implement int sqrt(int x).

Compute and return the square root of x.

Solution:

1. Binary search

Set d=x/m, if d>m, then the answer should be between d and m, else should be between m and d. Keep searching till Math.abs(d-m)<=1. 

Time complexity: O(logx)

 public int sqrt(int x) {  
    if(x<=0) return 0;  
    int l=1;  
    int r=x;  
    while(l<=r){  
      int m=(r-l)/2+l;  
      int d=x/m;  
      if(Math.abs(m-d)<=1) return Math.min(m,d);  
      else if(m>d){  
        l=d+1;  
        r=m-1;  
      }  
      else {  
        l=m+1;  
        r=d-1;  
      }  
    }  
    return r;  
   }  

2. Newton's Method
The essential of this problem is to find the solution for this equation y^2-x=0, f(y)=y^2-x, while f'(y)=2*y. So the process is repeated as y[n+1]= y[n]-(y[n]-x/y[n])/2.

  public int sqrt(int x) {  
     if(x<0) return Integer.MIN_VALUE;  
     if(x<=1) return x;  
     int y=x/2;  
     while(Math.abs(y-x/y)>1){  
       y=y-(y-x/y)/2;  
     }  
     return Math.min(y,x/y);  
   }