力扣刷题——二分查找实现pow幂函数

Bertha 。 2022-10-23 11:20 167阅读 0赞

1、先来个例题：  
![在这里插入图片描述][20210305105339373.png]

取值范围：

*  \-100.0 < x < 100.0
 *  \-231 <= n <= 231-1

> 举个例子：  
> 输入：x=2 n=10  
> 输出：1024  
> 输入：x=2 n=-2  
> 输出：0.25 （因为1/4=0.25）

给出方法

public double myPow(double x, int n) { 
    }

2、分析

**思路一：**

*蛮力法*

根据幂函数定义直接求解，即2的10次方=2 \* 2 \*… \* 2（10个2相乘）

代码实现：略

优点：思路清晰，简单直接易懂。  
缺点：时间复杂度O(n)，当n足够大时，程序运行超时。

按照目前思路，没有太多优化提升的余地。  
  
  
  
  
**思路二：**  
*减治法-二分查找*

减治法的基本思路是，将当前实例的解与其较小实例解建立关系。

先看个例子：  
![在这里插入图片描述][2021030511341372.png]

当n>0时，  
1）n是偶数，求解等价于(n/2)^2，比如上面的10/2=5。  
2）当n是奇数，等价于x \* x^(n-1)，  
比如  
![在这里插入图片描述][2021030514275490.png]

当n<0时，  
![2^(-2)=1/(2^2)][2_-2_1_2_2]

基本类似n>=0的情况。

当n=0时，直接返回1。

**代码实现：**

第一版

public double myPow(double x, int n) { 
             while(n>=1 || n<=-1){ 
                if(n % 2==0){ 
                    n=n/2;
    
                    if(n>0){ 
                        return myPow(x,n)*myPow(x,n);
                    }else { 
                        n=-n;
                        return 1/myPow(x,n)*myPow(x,n);
                    }
                }else { 
                    if(n==1) return x;
                    if(n==-1) return 1/x;
                    if(n>0){ 
                        n--;
                        return x*myPow(x,n);
                    }else { 
                        n++;
                        n=-n;
                        return 1/(x*myPow(x,n));
                    }
    
                }
            }
            return 1;
        }

运行后仍然超时，稍微修改一下。

第二版

将下面这行代码
    return myPow(x,n)*myPow(x,n);
    修改为：
     double y=myPow(x,n);
     return y*y;

![在这里插入图片描述][20210305110128305.png]

> Tips：  
> 递归时，可使用变量，尽量减少递归的次数。否则容易出现栈溢出或超时等问题。

运行通过，缺点也很明显。代码有点冗长，分了三大种情况，可以继续抽象。  
  
  
  
  
第三版

public double quickMul(double x, long N) { 
            if (N == 0) { 
                return 1.0;
            }
            double y = quickMul(x, N / 2);
            return N % 2 == 0 ? y * y : y * y * x;
        }
    
        public double myPow(double x, int n) { 
            long N = n;
            return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
        }

与之前的版本相比：  
a. 更加充分的利用了递归的特性，不再需使用while。

b. 使用三目表达式  
减少了冗余繁琐的if…else…  
同样的，也增加的理解的难度。

c.更加抽象  
结束递归的口径唯一，进行了更多的抽象。代码更加简洁。

3、小结

二分查找是减治法的一个具体实现算法，他将求解n与n/2联系起来，找到之间关联。然后利用这种关联，加上结束条件（比如n=1或者n=0时，有已知值）。

旨在降低时间复杂度，提高运行效率。相应的，代码可能不太好理解。

[20210305105339373.png]: /images/20221023/e207c2d458534e099e81f0ba8d5c3aba.png
[2021030511341372.png]: /images/20221023/ecfc94aa557d4a20859e2aa494b24c79.png
[2021030514275490.png]: /images/20221023/09cf0cf060274d0ca75583045c7ddf46.png
[2_-2_1_2_2]: /images/20221023/4d65c575a41f4d1d8f14852396968f69.png
[20210305110128305.png]: /images/20221023/39ef348ff9b4482081472c703c6aba3a.png