-
Notifications
You must be signed in to change notification settings - Fork 2
/
069 Sqrt(x).java
60 lines (48 loc) · 1.32 KB
/
069 Sqrt(x).java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*
69. Sqrt(x)
https://leetcode.com/problems/sqrtx/
Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
Input: 4
Output: 2
Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.
*/
public class Solution {
public int mySqrt(int x)
{
if (x == 0)
{
return 0;
}
int lt = 1;
int rt = Integer.MAX_VALUE; // 2 ^ 31 - 1
while (lt <= rt)
{
// Not lt + rt >> 1, think integer overflow
int mid = (lt + (rt - lt >> 1));
// Not compare with mid * mid, think integer overflow
int div = x / mid;
if (mid == div)
{
return mid;
}
else if (mid < div)
{
lt = mid + 1;
}
else // mid > div
{
rt = mid - 1;
}
}
// As the break of binary search now, lt = rt + 1
// Choose smaller rt
return rt;
}
}