Yoru Karu Studio
Yoru Karu Studio

LeetCode 解題思路：69. Sqrt(x)（平方根）

掌握二分搜尋法求解整數平方根的技巧

luk 收錄於 Leetcode
 約 1500 字 預計閱讀 8 分鐘 

LeetCode 解題思路：Sqrt(x)（平方根）

題目描述

給定一個非負整數 x，返回 x 的平方根，結果向下取整到最接近的整數。返回的整數必須是非負的。

限制：你不能使用任何內建的指數函數或運算子。

  • 例如，在 C++ 中不能使用 pow(x, 0.5)
  • 在 Python 中不能使用 x ** 0.5

範例

範例 1：

輸入：x = 4
輸出：2
解釋：4 的平方根是 2，所以返回 2

範例 2：

輸入：x = 8
輸出：2
解釋：8 的平方根是 2.82842...，向下取整後返回 2

限制條件

  • 0 <= x <= 2³¹ - 1

核心概念

1. 問題本質分析

這道題本質上是要找到一個最大的整數 ans，使得 ans² <= x。

換句話說，我們要找到滿足以下條件的最大整數：

  • ans * ans <= x
  • (ans + 1) * (ans + 1) > x

2. 為什麼適合用二分搜尋？

關鍵洞察：平方根函數是單調遞增的！

如果 a < b，那麼 √a < √b。這種單調性使得二分搜尋成為理想的解法。

視覺化理解 

尋找 √8 的過程：

數軸: 0---1---2---3---4---5---6---7---8
      ↑               ↑               ↑
     left           mid             right

檢查 mid = 4: 4² = 16 > 8，太大了！
更新 right = mid - 1 = 3

數軸: 0---1---2---3
      ↑       ↑   ↑
     left   mid right

檢查 mid = 1: 1² = 1 < 8，可能的答案
更新 ans = 1, left = mid + 1 = 2

數軸: 2---3
      ↑   ↑
    left right
    mid

檢查 mid = 2: 2² = 4 < 8，可能的答案
更新 ans = 2, left = mid + 1 = 3

數軸: 3
      ↑
    left/right/mid

檢查 mid = 3: 3² = 9 > 8，太大了！
更新 right = mid - 1 = 2

結束：left > right，返回 ans = 2

解法一：二分搜尋法（推薦）

思路

  1. 設定搜尋範圍 [0, x]
  2. 不斷縮小範圍，找到最大的數使其平方不超過 x
  3. 記錄所有可能的答案，返回最後一個有效答案

程式碼實現 

class Solution:
    def mySqrt(self, x: int) -> int:
        # 特殊情況處理
        if x < 2:
            return x
        
        left, right = 0, x
        ans = 0
        
        while left <= right:
            # 防止溢位的中點計算方式
            mid = left + (right - left) // 2
            
            # 計算 mid 的平方
            square = mid * mid
            
            if square <= x:
                # mid 可能是答案，記錄下來
                ans = mid
                # 嘗試找更大的數
                left = mid + 1
            else:
                # mid 太大了，縮小範圍
                right = mid - 1
        
        return ans

優化版本：縮小搜尋範圍 

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        
        # 優化：√x <= x/2 當 x >= 4
        left, right = 2, x // 2
        
        while left <= right:
            mid = left + (right - left) // 2
            square = mid * mid
            
            if square > x:
                right = mid - 1
            elif square < x:
                left = mid + 1
            else:
                # 找到精確的平方根
                return mid
        
        # right 就是答案
        return right

執行過程詳解

讓我們詳細追蹤 x = 8 的執行過程：

初始狀態：
x = 8
left = 2, right = 4 (因為 8 // 2 = 4)

步驟 1：
mid = 2 + (4 - 2) // 2 = 3
square = 3 * 3 = 9
9 > 8，太大了
right = 3 - 1 = 2

步驟 2：
left = 2, right = 2
mid = 2
square = 2 * 2 = 4
4 < 8，可以
left = 2 + 1 = 3

步驟 3：
left = 3, right = 2
left > right，結束循環
返回 right = 2

解法二：牛頓迭代法（Newton’s Method）

數學原理

牛頓迭代法是求解方程 f(x) = 0 的經典方法。對於求平方根，我們要解的方程是： f(t) = t² - x = 0

牛頓迭代公式：

t_{n+1} = t_n - f(t_n) / f'(t_n)
       = t_n - (t_n² - x) / (2 * t_n)
       = (t_n + x / t_n) / 2

視覺化理解 

求 √8 的過程：

初始猜測: t₀ = 8
t₁ = (8 + 8/8) / 2 = 4.5
t₂ = (4.5 + 8/4.5) / 2 ≈ 3.14
t₃ = (3.14 + 8/3.14) / 2 ≈ 2.84
t₄ = (2.84 + 8/2.84) / 2 ≈ 2.83
...
收斂到 √8 ≈ 2.828...

程式碼實現 

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        
        # 初始猜測值
        t = x
        
        # 當 t² > x 時繼續迭代
        while t * t > x:
            # 牛頓迭代公式
            t = (t + x // t) // 2
        
        return t

浮點數版本（更精確） 

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        
        # 使用浮點數提高精度
        t = float(x)
        epsilon = 1e-10  # 精度要求
        
        while abs(t * t - x) > epsilon:
            t = (t + x / t) / 2
        
        return int(t)

解法三：暴力法（不推薦，但有教育意義）

思路

從 1 開始逐一檢查，直到找到第一個平方大於 x 的數。

程式碼實現 

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        
        for i in range(1, x + 1):
            if i * i > x:
                return i - 1
        
        return x  # 不會執行到這裡

為什麼不推薦？

時間複雜度是 O(√x)，對於大數字會很慢。例如 x = 2147483647，需要檢查約 46340 次。

解法四：位元操作法（進階）

思路

利用平方根的位元特性，從高位到低位逐位確定答案。

程式碼實現 

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        
        # 找到最高位
        # 對於 32 位整數，平方根最多 16 位
        ans = 0
        bit = 1 << 16  # 從 2^16 開始
        
        while bit > 0:
            ans |= bit
            # 如果 ans² > x，撤銷這一位
            if ans * ans > x:
                ans ^= bit
            bit >>= 1
        
        return ans

常見錯誤與陷阱

錯誤 1：整數溢位 

# ❌ 錯誤！可能溢位
def mySqrt(self, x: int) -> int:
    left, right = 0, x
    while left <= right:
        mid = (left + right) // 2  # 當 x 很大時可能溢位
        # ...

正確做法：

# ✅ 防止溢位
mid = left + (right - left) // 2

錯誤 2：邊界條件處理不當 

# ❌ 錯誤！沒有處理 x = 0 或 1
def mySqrt(self, x: int) -> int:
    left, right = 1, x  # x = 0 時會出錯
    # ...

錯誤 3：返回錯誤的答案 

# ❌ 錯誤！應該返回向下取整的結果
def mySqrt(self, x: int) -> int:
    # ... 二分搜尋 ...
    return mid  # 應該返回 ans 或 right

錯誤 4：牛頓法的精度問題 

# ❌ 錯誤！整數除法會損失精度
def mySqrt(self, x: int) -> int:
    t = x
    while t * t > x:
        t = (t + x / t) // 2  # 應該是 (t + x // t) // 2

進階思考

1. 求精確的浮點數平方根 

def sqrt_float(x: float, precision: float = 1e-10) -> float:
    if x < 0:
        raise ValueError("不能計算負數的平方根")
    if x == 0:
        return 0
    
    # 二分搜尋法
    left, right = 0.0, max(1.0, x)
    
    while right - left > precision:
        mid = (left + right) / 2
        if mid * mid > x:
            right = mid
        else:
            left = mid
    
    return (left + right) / 2

2. 求立方根 

def cubicRoot(x: int) -> int:
    if x == 0:
        return 0
    
    # 處理負數
    sign = 1 if x > 0 else -1
    x = abs(x)
    
    left, right = 0, x
    ans = 0
    
    while left <= right:
        mid = left + (right - left) // 2
        cube = mid * mid * mid
        
        if cube <= x:
            ans = mid
            left = mid + 1
        else:
            right = mid - 1
    
    return ans * sign

3. 求 n 次方根 

def nthRoot(x: int, n: int) -> int:
    if n == 1:
        return x
    if x == 0:
        return 0
    
    left, right = 0, x
    ans = 0
    
    while left <= right:
        mid = left + (right - left) // 2
        
        # 計算 mid^n，注意防止溢位
        power = 1
        for _ in range(n):
            if power > x // mid:  # 防止溢位
                power = x + 1
                break
            power *= mid
        
        if power <= x:
            ans = mid
            left = mid + 1
        else:
            right = mid - 1
    
    return ans

4. 判斷是否為完全平方數 

def isPerfectSquare(num: int) -> bool:
    if num < 0:
        return False
    
    root = mySqrt(num)
    return root * root == num

複雜度分析

解法一：二分搜尋

  • 時間複雜度：O(log x)
  • 空間複雜度：O(1)

解法二：牛頓迭代法

  • 時間複雜度：O(log x)，收斂速度極快（二次收斂）
  • 空間複雜度：O(1)

解法三：暴力法

  • 時間複雜度：O(√x)
  • 空間複雜度：O(1)

解法四：位元操作

  • 時間複雜度：O(log x)
  • 空間複雜度：O(1)

相關題目推薦

  1. LeetCode 367: Valid Perfect Square - 判斷完全平方數
  2. LeetCode 633: Sum of Square Numbers - 平方數之和
  3. LeetCode 50: Pow(x, n) - 計算 x 的 n 次方
  4. LeetCode 372: Super Pow - 超級次方
  5. LeetCode 279: Perfect Squares - 完全平方數
  6. LeetCode 1539: Kth Missing Positive Number - 二分搜尋應用

實戰技巧總結

1. 二分搜尋模板 

def binarySearch(condition):
    left, right = min_value, max_value
    result = default_value
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if condition(mid):
            result = mid  # 記錄可能的答案
            # 根據題目調整搜尋方向
            left = mid + 1  # 或 right = mid - 1
        else:
            # 調整另一個方向
            right = mid - 1  # 或 left = mid + 1
    
    return result

2. 防止溢位技巧 

# 計算中點
mid = left + (right - left) // 2

# 比較平方
if mid > x // mid:  # 等價於 mid * mid > x，但防止溢位
    # ...

# 累乘時檢查
product = 1
for _ in range(n):
    if product > MAX_VALUE // factor:
        # 會溢位
        break
    product *= factor

3. 調試技巧 

def mySqrt(self, x: int) -> int:
    print(f"計算 √{x}")
    
    if x < 2:
        return x
    
    left, right = 2, x // 2
    iterations = 0
    
    while left <= right:
        mid = left + (right - left) // 2
        square = mid * mid
        
        print(f"迭代 {iterations}: [{left}, {right}], mid={mid}, mid²={square}")
        
        if square > x:
            right = mid - 1
        elif square < x:
            left = mid + 1
        else:
            print(f"找到精確平方根: {mid}")
            return mid
        
        iterations += 1
    
    print(f"返回向下取整結果: {right}")
    return right

4. 完整測試案例 

def test_mySqrt():
    test_cases = [
        (0, 0),
        (1, 1),
        (2, 1),
        (3, 1),
        (4, 2),
        (5, 2),
        (8, 2),
        (9, 3),
        (10, 3),
        (15, 3),
        (16, 4),
        (17, 4),
        (100, 10),
        (101, 10),
        (2147483647, 46340)  # 最大測試案例
    ]
    
    solution = Solution()
    for x, expected in test_cases:
        result = solution.mySqrt(x)
        status = "✅" if result == expected else "❌"
        print(f"{status} √{x} = {result} (期望: {expected})")

效能比較 

import time

def benchmark_methods(x):
    methods = [
        ("二分搜尋", mySqrt_binary),
        ("牛頓迭代", mySqrt_newton),
        ("位元操作", mySqrt_bit)
    ]
    
    for name, func in methods:
        start = time.time()
        result = func(x)
        elapsed = time.time() - start
        print(f"{name}: {result}, 耗時: {elapsed:.6f}秒")

總結

這道平方根問題展示了多種經典演算法：

  1. 二分搜尋：最通用、最容易理解的方法
  2. 牛頓迭代法：數學優雅、收斂快速
  3. 位元操作：利用位元特性的巧妙方法
  4. 暴力法：雖然低效，但有助於理解問題

關鍵要點：

  • 理解問題本質：找最大的數使其平方不超過 x
  • 選擇合適的演算法：二分搜尋是最平衡的選擇
  • 注意邊界條件：特別是 0 和 1
  • 防止整數溢位：使用安全的中點計算
  • 返回正確結果：向下取整

練習建議

  1. 基礎練習：

    • 手動模擬二分搜尋過程
    • 實現不同版本的解法
    • 處理各種邊界情況

  2. 進階練習：

    • 實現浮點數版本
    • 嘗試其他數值方法（如割線法）
    • 優化牛頓法的初始猜測

  3. 擴展練習：

    • 實現其他根號運算（立方根、n次方根）
    • 解決相關的數學問題
    • 研究快速平方根倒數演算法

  4. 應用練習：

    • 在圖形計算中使用（距離計算）
    • 在物理模擬中應用
    • 優化遊戲引擎中的計算

記住：數學問題往往有多種優雅的解法，選擇最適合場景的那一個！

更新於 2024-12-29 
CC BY-NC-SA 4.0
閱讀原始文檔
LeetcodeAlgorithmBinary-SearchMath
返回 | 主頁
0%