今天是紀錄LeetCode解題的第六十九天

第六十九題題目：Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

• For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

給定一個非負整數x，傳回其向下取整到最接近的整數的平方根，不能使用任何內建的指數函數或運算符

• 例如，不要在c++中使用pow(x, 0.5)或在python中使用x ** 0.5

解題思路

暴力法
要找出平方根，只要遍歷i = 1 ~ x // 2 + 2(+2是要找0跟1的平方根的時候，讓迴圈可以跑)的範圍就好，當i * i == x則直接回傳i，i * i > x回傳i - 1

二分搜尋
先排除0和1的平方根情況，遇到x < 2都直接回傳x
我們知道平方根的範圍落在1 ~ x // 2，令left = 1、right = x // 2，算出他的中間值mid，當mid * mid == x直接回傳mid，如果小於x，則將left = mid + 1，反之right = mid - 1，最後回傳right

牛頓法
先排除0和1的平方根情況，遇到x < 2都直接回傳x

程式碼

暴力法

class Solution:
    def mySqrt(self, x: int) -> int:
        for i in range(1,x // 2 + 2):
            if i * i > x:
                return i - 1
            elif i * i == x:
                return i

二分搜尋

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

牛頓法

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        r = x
        while r * r > x:
            r = (r + x // r) // 2
        return r

執行過程(x = 8)

暴力法
i = 1

• if i * i > x → 1 * 1 > 8 → False

i = 2

• if i * i > x → 2 * 2 > 8 → False

i = 3

• if i * i > x → 3 * 2 > 3 → True
• return i - 1 → return 2

二分搜尋

• left = 1
• right = 4
• mid = (left + right) // 2 → mid = (1 + 4) // 2 = 2
• elif mid * mid < x → 2 * 2 < 8 → True
• left = mid + 1 = 3

• mid = (left + right) // 2 → mid = (3 + 4) // 2 = 3
• right = mid - 1 → right = 2
• return right → return 2

牛頓法

• r = x = 8
• r = (r + x // r) // 2 → r = (8 + 1) // 2 = 4
• r = (r + x // r) // 2 → r = (4 + 2) // 2 = 3
• r = (r + x // r) // 2 → r = (3 + 2) // 2 = 2
• return r → return 2

牛頓法在x非常大的時候會比暴力法跟二分搜尋法還要來的快非常多，因為牛頓法是二次收斂，誤差平方級的減少，也就是說每次迭代誤差會變成上次誤差的平方，所以會非常快地找到我們要求的值