劍指 Offer 面試題 11：數值的整數次方 - 遞歸分治 O(log n) 高效實作

經典面試題：實作 double Power(double base, int exponent)，不使用庫函數，處理底數為 0、指數為負數等邊界情況。本文提供兩種解法：迭代 O(n) 與 遞歸分治 O(log n)，完整程式碼含詳細邊界檢查與測試用例。

題目要求

• 實作 power(base, exponent)
• 底數 base 為 double，指數 exponent 為 int
• 不得使用 Math.pow() 等庫函數
• 不考慮大數溢位
• 完整處理 9 種組合：底數正/負/零 × 指數正/負/零
• 特別注意：base == 0 且 exponent < 0 無意義，拋異常

核心演算法：遞歸分治

利用數學性質將計算量從 O(n) 降為 O(log n)：

a^n = (a^(n/2))^2                    , n 為偶數
a^n = (a^(n/2))^2 * a                , n 為奇數
a^0 = 1
a^1 = a

位運算優化：

• n >> 1 等價 n / 2
• (n & 0x1) == 1 判斷奇數
• ~exponent + 1 取絕對值（避免 Integer.MIN_VALUE 溢位）

完整程式碼實作

package Solution;

public class No11Power {

    public static void main(String[] args) {
        // 9 種組合測試
        System.out.println("底數 2，指數 2："   + power(2, 2));
        System.out.println("底數 2，指數 -2："  + power(2, -2));
        System.out.println("底數 2，指數 0："   + power(2, 0));
        System.out.println("底數 -2，指數 2："  + power(-2, 2));
        System.out.println("底數 -2，指數 -2：" + power(-2, -2));
        System.out.println("底數 -2，指數 0："  + power(-2, 0));
        System.out.println("底數 0，指數 2："   + power(0, 2));
        System.out.println("底數 0，指數 0："   + power(0, 0));
        System.out.println("底數 2，指數 1："   + power(2, 1));
        System.out.println("底數 0，指數 -2："  + power(0, -2)); // 拋異常
    }

    public static double power(double base, int exponent) {
        // 邊界：0 的負次方無意義
        if (equal(base, 0.0) && exponent < 0)
            throw new RuntimeException("指數為負數時，底數不能為 0");

        int absExponent = exponent;
        if (exponent < 0)
            absExponent = ~exponent + 1;  // 位運算取絕對值，避免 MIN_VALUE 溢位

        // 遞歸分治核心
        double result = powerWithUnsignedExponentByRecursion(base, absExponent);

        // 負指數取倒數
        if (exponent < 0)
            result = 1.0 / result;

        return result;
    }

    // 解法一：迭代 O(n) - 教學參考
    private static double powerWithUnsignedExponent(double base, int absExponent) {
        double result = 1.0;
        for (int i = 1; i <= absExponent; i++)
            result *= base;
        return result;
    }

    // 解法二：遞歸分治 O(log n) - 推薦
    private static double powerWithUnsignedExponentByRecursion(double base, int exponent) {
        if (exponent == 0) return 1.0;
        if (exponent == 1) return base;

        double half = powerWithUnsignedExponentByRecursion(base, exponent >> 1);
        double result = half * half;
        if ((exponent & 0x1) == 1)  // 奇數
            result *= base;
        return result;
    }

    // 浮點數比較：設定精度閾值
    private static boolean equal(double num1, double num2) {
        return (num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001);
    }
}

關鍵細節深度解析

1. 浮點數零值判斷

不可用 base == 0.0，因浮點數精度誤差。引入 equal() 以 1e-7 為閾值判斷「相等」。

2. Integer.MIN_VALUE 絕對值溢位問題

Math.abs(Integer.MIN_VALUE) 仍為負數。用 ~exponent + 1（補碼取反加一）正確得到正數絕對值。

3. 遞歸終止條件

• exponent == 0 → 返回 1.0
• exponent == 1 → 返回 base

避免無限遞歸並正確處理奇數情況。

4. 負指數處理流程

1. 先按正指數計算
2. 最後 1.0 / result 取倒數

複雜度分析

面試加分點

1. 主動提及 Integer.MIN_VALUE 絕對值溢位並給出位運算解法
2. 說明浮點數比較需設定 epsilon
3. 指出遞歸版空間複雜度 O(log n) 及棧溢位風險，補充迭代版二分冪實作思路
4. 完整列舉 9 種邊界測試用例展示測試思維

結語

這道題不僅考察基本編碼能力，更考察對邊界條件、數值計算陷阱、演算法優化的綜合掌握。遞歸分治 O(log n) 解法配合完善邊界處理，是面試中的標準滿分答案。