2.19 Sqrt(x)

Description

Implement int sqrt(int x).

Compute and return the square root of x.

Method

ONE : for loop from 1 to sqrt(x)

two : binary search (1, Integer.MAX_VALUE)

Time and Space Complexity

(sqrt(n)) (log(MAx))

Code

public class Solution {

 public int mySqrt(int x) {
       if (x == 0){
           return 0;
       }
    //   int i = 1;

    //   for (; i <= x / i; i++){

    //   }
       int left = 1;
       int right = Integer.MAX_VALUE;
       while (true){
           int mid = (right - left) / 2 + left;
           if (mid > x / mid){
               right = mid - 1;
           } else {
                if (mid + 1 > x / (mid + 1)){ 
                    return mid;
                   }
               left = mid + 1;
           } 
       }
}

}