69 Sqrt(x)

69. Sqrt(x)

1. Question

Implementint sqrt(int x).
Compute and return the square root ofx.
x is guaranteed to be a non-negative integer.
Example 1:
1
Input: 4
2
3
Output:2
Copied!
Example 2:
1
Input: 8
2
3
Output: 2
4
5
Explanation:
6
The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will betruncated.
Copied!

2. Implementation

(1) Binary Search
思路:由于这题要求结果是整数,这就相当于找一个整数num <= sqrt(x), 是找右边界, 可以直接套用二分法的找右边界的模板
1
class Solution {
2
public int mySqrt(int x) {
3
if (x == 0) {
4
return 0;
5
}
6
7
int start = 1, end = x, mid = 0;
8
9
while (start + 1 < end) {
10
mid = start + (end - start) / 2;
11
12
if (mid > x / mid) {
13
end = mid - 1;
14
}
15
else {
16
start = mid;
17
}
18
}
19
20
if (end <= x / end) {
21
return end;
22
}
23
else {
24
return start;
25
}
26
}
27
}
Copied!

3. Time & Space Complexity

Binary Search: 时间复杂度O(logx), 空间复杂度O(1)