實現?int sqrt(int x)?函數。

計算并返回?x?的平方根，其中?x 是非負整數。

由于返回類型是整數，結果只保留整數的部分，小數部分將被舍去。

示例 1:

輸入: 4
輸出: 2
示例 2:

輸入: 8
輸出: 2
說明: 8 的平方根是 2.82842...,?
?? ? 由于返回類型是整數，小數部分將被舍去。

解法：

class Solution {
public:int mySqrt(int x) {long long left = 0, right = x;while(left < right){long long mid = left + (right - left) / 2;if(mid * mid <  x)left = mid + 1;elseright = mid;}if(left * left == x) return left;else return left -1;}
};