leetcode-javascript-69. x 的平方根

求边界
（a/2）^2 >= a => a >= 4， a < = 0
大多数情况注意JavaScript 的Math.floor
还有leetcode的JavaScript可能对>>不支持
所有的数都放在一起考虑，为了照顾到 00 把左边界设置为 00，为了照顾到 11 把右边界设置为 x // 2 + 1。

• 不可以取左边区间的原因、0到4的数会出现无限循环的情况要特别注意
  此时索引区间 [3, 4] 的中位数为左中位数，即 mid = 3 ，此时 square = 9 < 9 不成立，进入 left = mid 这个分支，你发现问题了吗，区间不发生收缩，即下一轮循环的索引区间还是 [3, 4]，此时中位数还取左中位数，即 mid = 3 ，square = 9 < 9 不成立，又进入 left = mid 这个分支，死循环就是这样产生的。
  没有多以收缩空间，3，4当进入 下一个收缩时

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    // return Math.floor(Math.sqrt(x))
    let left = 0;
    let right = Math.floor(x/2) + 1;
    while(left < right) {
        let mid = left + Math.floor((right - left + 1)/2)//一定要+1取右边
        // console.log()
        let sq = mid * mid
        if(sq > x) {
            right = mid - 1 //
        }else{
            left = mid
        }
        
    }
    return left
};
class Solution:

    def mySqrt(self, x):
        left = 0
        right = 999999
        while left < right:
            # 这种取中位数的方法又快又好，是我刚学会的，原因在下面这篇文章的评论区
            # https://www.liwei.party/2019/06/17/leetcode-solution-new/search-insert-position/
            mid = (left + right + 1) >> 1
            square = mid * mid
            if square > x:
                right = mid - 1
            else:
                left = mid

        return left
class Solution:
    def mySqrt(self, x: int) -> int:
        # 为了照顾到 0 把左边界设置为 0
        left = 0
        # 为了照顾到 1 把右边界设置为 x // 2 + 1
        right = x // 2 + 1
        while left < right:
            # 注意：这里一定取右中位数，如果取左中位数，代码可能会进入死循环
            # mid = left + (right - left + 1) // 2
            mid = (left + right + 1) >> 1
            square = mid * mid

            if square > x:
                right = mid - 1
            else:
                left = mid
        # 因为一定存在，因此无需后处理
        return left  

牛顿法