# sqrt(x)

## sqrt(x)

### Special binary search problem

Left bound is zero, and right bound is `max(x/2,1)`

. Then do the binary search to find out the result. Some corner cases should be taken care of.

- When the target is 1, so we use
`max(x/2,1)`

. - When we caculate
`mid*mid`

, this may beyond the bound of`int`

, we need use`long long`

insteand of`int`

. - When we write the comparative expression, put
`long long`

at left.

```
1 class Solution {
2 public:
3 int sqrt(int x) {
4 long long left = 0;
5 long long right = max(x/2,1);
6 long long mid = 0;
7 while ( left <= right ) {
8 mid = left+(right-left)/2;
9 if ( mid*mid > x ) {
10 right = mid-1;
11 }
12 if ( mid*mid == x ) {
13 return mid;
14 }
15 if ( mid*mid < x && (mid+1)*(mid+1) > x ) {
16 return mid;
17 }
18 if ( (mid+1)*(mid+1) == x ) {
19 return mid+1;
20 }
21 if ( (mid+1)*(mid+1) < x ) {
22 left = mid+1;
23 }
24 }
25 }
26 };
```