题目：
Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.
You must not use any built-in exponent function or operator.
For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.
Example 1:
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.
Example 2:
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842…, and since we round it down to the nearest integer, 2 is returned.
Constraints:
0 <= x <= 231 - 1
思路：
输入的是一个非负数x，需要返还x的开平方，并且需要是一个向下约的整数。
我们可以使用binary search去完成这个题目。
从[0, x]这个范围开始做binary search，首先检查中间点mid。
如果mid的2次方是x，那么mid就正好是x的开平方。
如果mid的2次方要小于x，证明应该向右移动mid，去找更大的数，将low更新为mid+1。
如果mid的2次方要大于x，证明应该向左移动mid，去找更小的数，将high更新为mid-1。
这个解决方案的time complexity是O(log x)。
class Solution(object):def mySqrt(self, x):""":type x: int:rtype: int"""if x == 0 or x == 1:return xlow, high = 0, xresult = 0while low <= high:mid = (low + high) // 2if mid * mid == x:return midelif mid * mid < x:low = mid + 1result = midelif mid * mid > x:high = mid - 1return result
