题目

题解

这道题是实现一个Math.sqrt()函数。要使用二分算法，二分算法算是双指针中的一种特殊情况。按照双指针的解法，我们先确定指针指向初始值，左指针不用说指向最小值也就是1，而右指针的指向就需要考虑一下啦，如何让搜索范围变小。你会发现平方根会在x的左侧出现。那吗可以将右指针指向x的一半。但是二分算法有两种情况，一种树奇数情况下，一种就是在偶数的情况下。奇数不用说，偶数的情况下会有两个值，我们应该取那个值？题目给出的是，只保留整数部分，小数部分直接去掉，那就是要偶数情况下的左值。
图例偶数情况下

二分

/**
 * @param {number} x
 * @return {number}
 * 平方根在 x一半的左侧
 */
var mySqrt = function(x) {
    if(x < 2) return x;
    let l = 1;
    let r = x >> 1;
    let mid = 0;
    let square = 0;
    while(l <= r) {
        mid = (l + r) >> 1;
        square = mid * mid;
        if(square == x) return mid;
        else if (square > x) r = mid - 1;
        else l = mid + 1
    }
    // 结束条件是 l 大于 r 那吗r会比l小，题意中是只保留整数部分，舍去小数，故取小值也就是r
    return r
};