[Leetcode] Sqrt(x)

Problem

Implement int sqrt(int x). Compute and return the square root of x. 

For example, sqrt(9) = 3, sqrt(10) = 3, and sqrt(16) = 4. 

Algorithm

Let y  = sqrt(x), where y is an integer. Calculating the sqrt(x) is  equivalent to find a y that satisfies 

                                                              y^2 <= x < (y+1)^2. 

Start with y=x, we can reduce y one by one until it satisfies the relation above. This algorithm takes O(n) time. 

Using the idea of binary search, the have the code below, which has O(log(n)) time. 

Be careful about the integer overflow. 

Be careful about the corner case x = 0. 

Code