Sqrt(x) 解答

Question

Implement int sqrt(int x).

Compute and return the square root of x.

Solution 1 -- O(log n)

常规做法是用的binary search。注意这里mid一定要是long类型，否则mid * mid会溢出。

 1 public class Solution {
 2     public int mySqrt(int x) {
 3         // Use long instead of int
 4         long start = 1, end = x, mid;
 5         while (start + 1 < end) {
 6             mid = (end - start) / 2 + start;
 7             long tmp = mid * mid;
 8             if (tmp == x) {
 9                 return (int) mid;
10             } else if (tmp < x) {
11                 start = mid;
12             } else {
13                 end = mid;
14             }
15         }
16         if (end * end <= x)
17             return (int) end;
18         return (int) start;
19     }
20 }

Solution 2 -- Constant Time

我们可以通过以下数学公式缩小问题规模：

因此，问题转换成如何求 log₂N

注意到对于任何数，它的binary representation可以表示为Σ2ⁱ

所以 log₂N 的取值范围为[i, i + 1] i 为最高位的位数。

因此我们就缩小了二分查找的范围。

 1 public class Solution {
 2     public int mySqrt(int x) {
 3         int num = x, digit = 0;
 4         while (num > 0) {
 5             num = num >> 1;
 6             digit++;
 7         }
 8         int candidate1 = (int) Math.pow(2, 0.5 * digit);
 9         int candidate2 = (int) Math.pow(2, 0.5 * (digit - 1));
10         long start = candidate2, end = candidate1, mid;
11         while (start + 1 < end) {
12             mid = (end - start) / 2 + start;
13             long tmp = mid * mid;
14             if (tmp == x)
15                 return (int) mid;
16             if (tmp < x)
17                 start = mid;
18             else
19                 end = mid;
20         }
21         if (end * end <= x)
22             return (int) end;
23         return (int) start;
24     }
25 }