Implement int sqrt(int x).

Compute and return the square root of x.

Have you met this question in a real interview? 

Yes

Example

sqrt(3) = 1

sqrt(4) = 2

sqrt(5) = 2

sqrt(10) = 3

1 class Solution { 2     /** 3      * @param x: An integer 4      * @return: The sqrt of x 5      */ 6     public int sqrt(int x) { 7         long start = 0; 8         long end = x; 9 10         while (start <= end) {11             long mid = start + (end - start) / 2;12             if (mid * mid == x) {13                 return (int) mid;14             } else if (mid * mid < x) {15                 start = mid + 1;16             } else {17                 end = mid - 1;18             }19         }20         return (int)(start - 1);  // we are looking for lower end.21     }22 }

or we can do it another way.

1 class Solution { 2     /** 3      * @param x: An integer 4      * @return: The sqrt of x 5      */ 6     public int sqrt(int x) { 7         long start = 0; 8         long end = x; 9 10         while (start <= end) {11             long mid = start + (end - start) / 2;12             if (mid * mid == x) {13                 return (int) mid;14             } else if (mid * mid < x && (mid + 1) * (mid + 1) > x) {15                 return (int) mid;16             } else if (mid * mid < x) {17                 start = mid + 1;18             } else {19                 end = mid - 1;20             }21         }22         return -1;23     }24 }