141. Sqrt(x) 【easy】

141. Sqrt(x) 【easy】

Implement int sqrt(int x).

Compute and return the square root of x.

Example

sqrt(3) = 1

sqrt(4) = 2

sqrt(5) = 2

sqrt(10) = 3

Challenge

O(log(x))

解法一：

 1 class Solution {
 2 public:
 3     /*
 4      * @param x: An integer
 5      * @return: The sqrt of x
 6      */
 7     int sqrt(int x) {
 8         // write your code here
 9         long start = 1;
10         long end = x;
11         
12         while (start + 1 < end) {
13             long mid = start + (end - start) / 2;
14             
15             if (mid * mid == x) {
16                 return mid;
17             }
18             else if (mid * mid < x) {
19                 start = mid;
20             }
21             else if (mid * mid > x) {
22                 end = mid;
23             }
24         }
25         
26         if (end * end <= x) {
27             return end;
28         }
29         else {
30             return start;
31         }
32     }
33 };

注意：

1、start、end、mid用long类型防止溢出

2、最后判断end * end与x的关系时要考虑等号，否则输入数值为0的时候就错了。

解法二：

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

这里还是两头都判断一下比较保险。