# 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 };``````