69. Sqrt(x)

Leetcode link

题目简介

/**
 * @param {number} x
 * @return {number}
 */

题目给我们一个数字 x

要求我们返回 x 的平方根向下取整的整数

不允许用内置函数

解题思路

求平方根不用内置函数的话，我们只能一个一个试，但是一个一个试也可以优化成二分搜索

首先确定左边界 left = 0、其次确定右边界 right = x >> 1（因为平方根绝对不会超过 x/2）

接着我们进行二分搜索，注意最后要返回 right，因为我们需要向下取整

Javascript

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
    if(x < 2) {
        return x
    }

    let left = 1
    let right = x >> 1

    while(left <= right) {
        const mid = left + ((right-left) >> 1)
        const square = mid * mid

        if(square === x) {
            return mid
        } else if(square < x) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return right
};

复杂度分析

时间

O(logx)

空间

O(1)