Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

We use binary search between [0,n]. But the return strategy change; Instead of mid== target, we will return if mid^2 <= x and (mid + 1)^2 > x: this means sqrt(x) is between mid^2 and (mid + 1)^2.

```
int mySqrt(int x) {
int upper = x;
int lower = 0;
long long mid = 0;
while(upper >= lower){
mid = lower + int((upper - lower) / 2);
if ((mid * mid) <= x and (mid + 1) * (mid + 1) > x){
return mid;
}
else if(mid * mid > x){
upper = mid - 1;
}
else if ( mid *mid < x)
lower = mid + 1;
}
return -1;
}
```

# A note on binary search

When we set new high and new low, remember to exclude the middle, because the fact we skipped the first if statement means that middle is definitely not a candidate.

```
high = mid - 1
low = mid + 1
```

# Math

https://en.wikipedia.org/wiki/Integer_square_root#Using_only_integer_division