[LeetCode] Sqrt(x)

Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Solution: Binary Search!
Suppose a = (int)sqrt(x), then a^2 <= x < (a+1)^2.
Pay attention to overflow.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

public class Solution { public int mySqrt(int x) { if (x <= 1) { return x; } int low = 1; int high = x; while (low <= high) { int mid = low + (high - low) / 2; if (x / mid >= mid && x / (mid + 1) < mid + 1) { return mid; } if (x / mid < mid) { high = mid - 1; } else { low = mid + 1; } } return 0; } }