> For the complete documentation index, see [llms.txt](https://blessbingo.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blessbingo.gitbook.io/garnet/suan-fa/shu-xue/50-shu-zhi-de-zheng-shu-ci-fang.md).

# \[50]\[中等]\[二分] Pow(x, n)

## 题目描述

[50. Pow(x, n)](https://leetcode-cn.com/problems/powx-n/) [剑指 Offer 16. 数值的整数次方](https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/)

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:

```
输入: 2.00000, 10
输出: 1024.00000
```

示例 2:

```
输入: 2.10000, 3
输出: 9.26100
```

示例 3:

```
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
```

说明:

* -100.0 < x < 100.0
* n 是 32 位有符号整数，其数值范围是 $$\[−2^{31}, 2^{31} − 1]$$ 。

## 解题思路

题目的意思是使用**最少次数**的加减乘除法计算结果. 因此思路是对幂不断的进行二分. 对于偶数幂`n`, 结果为`n // 2`幂结果的平方; 对于奇数幂, 结果为`n // 2`幂结果的平方, 再乘以一个原数`x`.

### 递归

```python
class Solution:
    def myPow(self, x: float, n: int) -> float:
        def dfs(exp):
            if exp == 0:
                return 1.0
            odd, half = exp % 2, exp // 2
            y = dfs(half)
            return y * y if not odd else y * y * x
        return dfs(n) if n >= 0 else 1.0 / dfs(-n)
```