LeetCode 解題練習：Sqrt(x)

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/sqrtx/

中文描述

給一個非負整數 x ，求出最接近但不大於  x 平方根的整數。注意，不能使用內建函式。

範例一：

輸入 x = 9

輸出 3

範例二：

輸入 x = 22 

輸出  4

因為 x 的平方根為 4.69041575982，取整數部分為 4 。

解法一：線性搜尋

r  = 1 開始判斷到 r * r <= x，傳回 r - 1。 

Python Code

class Solution:

    def mySqrt(self, x: int) -> int:

        r = 1

        while r * r <= x:

            r += 1

       

        return r - 1

解法二：二分搜尋

此部分可參考此教學影片的說明 https://www.youtube.com/watch?v=1_4xlky3Y2Y

Python Code

class Solution:

    def mySqrt(self, x: int) -> int:

        left = 1

        right = x

        while left <= right:

            middle = (left + right) // 2

            pow2 = middle * middle

            if pow2 == x:

                return middle

            elif pow2 < x:

                left = middle + 1

            else:

                right = middle - 1

           

        return right