求x的平方根，第一想法可能是遍历0～x，求其平方，找到或
且
但其时间复杂度为O(n)，或是想到遍历0～M即可，其中M = x // 2，将时间复杂度降至O(
)。本文利用二分思想，给出一种时间复杂度为O(logn)的代码实现，当x=10000时时间复杂度O(logn)远小于O(
)。
示例：
图1 平方根输入输出示例图
代码：
python">class Solution:def mySqrt(self, x):if x == 0:return 0l, r = 0, xres = 0while l <= r:m = (l + r) // 2if m**2 > x:r = m - 1elif m**2 < x:l = m + 1res = melse:return mreturn res解释：
1）只需注意一点，当m**2 < x时要及时更新res，因为可能不存在的情况，这是返回的应该是
且
情况下的m。
