Sqrt(x)

06/28/2016 Binary Search Math

Question

Implement int sqrt(int x).

Compute and return the square root of x.


Solution

Result: Accepted Time: 4 ms

Here should be some explanations.

int mySqrt(int x) {
    int low = 1,up = x;
    while(low < up)
    {
        up  = low + ((up -low) >> 1);
        low = x / up;
    }
    return up;
}

Complexity Analytics

  • Time Complexity:
  • Space Complexity: