LeetCode 筆記 - 69. Sqrt(x)

Posted on
實作求取整數平方根的功能。本文解析如何運用二元搜尋（Binary Search）在 0 到 x 的範圍內快速逼近目標值。這展示了二元搜尋不僅可用於數列尋找，也能應用在數學函數的根值逼近任務中，提供極高的計算效率。

題目在此 69. Sqrt(x)

給定一個數字，請給出平方根的整數部分

解題思維

這題就是典型的 Binary Search 的應用題

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def mySqrt(self, x: int) -> int:
        
        start = 0
        end = x
        
        while start <= end:
            
            mid = (start + end) // 2
            check_num = mid ** 2
            
            if check_num <= x < (mid + 1) ** 2:
                return mid
            elif x < check_num:
                end = mid - 1
            else:
                start = mid + 1

也許你也會想看看