Datawhale leetcode day1 NO.69_x 的平方根

一个数 x 的开方 sqrt 一定在 0 ~ x 之间，并且满足 sqrt == x / sqrt 。可以利用二分查找在 0 ~ x 之间查找 sqrt。

class Solution:
    def mySqrt(self, x: int) -> int:
        if x <= 1:
            return x;
        l = 1;
        h = x;
        while l <= h:
            mid = l + (h - l) // 2;
            sqrt = x / mid;
            if sqrt == mid:
                return mid;
            else:
                if sqrt < mid:
                    h = mid - 1;
                else: 
                    l = mid + 1;
        return h;

思想就是if $sqrt &lt; mid$sqrt<mid:，说明$mid*mid&gt;x$mid∗mid>x，要让$mid$mid变小一点，于是$h = mid - 1$h=mid−1;，下次$mid = l + (h - l) // 2$mid=l+(h−l)//2;的时候$mid$mid才会变小，
同理if $sqrt &gt; mid$sqrt>mid:，说明$mid*mid&lt;x$mid∗mid<x了，要让$mid$mid变大一点，于是$l = mid + 1$l=mid+1;，当两个界$low$low和$high$high重叠时，即$l=h$l=h，那么此时的$mid*mid$mid∗mid是大于$x$x且最近接$x$x的数，于是$h-1$h−1即为所求。

最后必将收敛到$l=k,h=k+1$l=k,h=k+1的形式，因为x会夹在两个平方数$k^2$k2和$（k+1）^2$（k+1）2之间，最后$mid=k,mid^2&lt;x$mid=k,mid2<x，对应$sqrt&lt;mid$sqrt<mid，$h=k$h=k，return $h$h正合适