六十八、快速幂算法、牛顿迭代法、累加数组+二分查找的变形

「@Author：Runsen」

❝

编程的本质来源于算法，而算法的本质来源于数学，编程只不过将数学题进行代码化。「---- Runsen」

❞

上次介绍了二分查找算法及其四个变形问题，下面介绍二分法常用的场景和典型的例题。

快速幂算法

题目是来自Leetcode：50. Pow(x, n)，https://leetcode-cn.com/problems/powx-n/

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

示例 1:

输入: 2.00000, 10
输出: 1024.00000

其实快速幂相关的问题，个人觉得只要你是一名程序员，就必须要掌握快速幂算法。

当我们遇到一个问题需要让我们求得一个数 n 的 m 次方，那么最简单的方法是将 n 乘以 m 次，得到结果，但是如果我们现在需要计算的是 2^10000000 这样的式子呢，显然如果我们的程序需要计算 2 的更高次方的时候这样的算法，对于算法竞赛而言时间上显然是不允许的，因此提出了快速幂算法。

其实在计算这样的式子的时候有大量的运算步骤是可以避免的，我们现在拿 次方举例：

按照上面的计算式，计算这样的式子，我们需要进行 8 次计算。

那么如果我们换一种思路来计算呢：，我们需要进行 2 次计算。

快速幂实际上是分治思想的一种应用。因此，可以得到：

下面就需要判断n/2的奇偶的情况。

观察发现，当 n 为奇数时，二分后会多出一项 x 。比如：。

当n为奇数，。

当n为偶数，

根据推导，每次把幂从 n 降至 n//2 ，直至将幂降为 0 。

如果x = 0时：直接返回0，初始化 res = 1，

n = 5
x = 3
res = 1
while n:
  if n % 2 == 1:
    res *= x
  x *= x
  n //= 2
print(res)

243

我们可以使用位运算写成比较高级的代码。

快速幂算法如果x等于0，直接返回0。如果小于0 ，x需要取其倒数，n取其相反数。

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0.0 : return 0.0
        res = 1
        if n < 0: x, n = 1 / x, -n
        while n:
            if n & 1: res *= x
            x *= x
            n >>= 1
        return res

求x的平方根

题目是来自LeetCode 第 69题：x 的平方根，https://leetcode-cn.com/problems/sqrtx/

计算并返回 x 的平方根，其中 x 是非负整数。

# 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。 
# 示例 1: 
# 输入: 4
# 输出: 2
# 示例 2: 
# 输入: 8
#输出: 2
#说明: 8 的平方根是 2.82842..., 
#     由于返回类型是整数，小数部分将被舍去。

二分查找的下界为 0

这个题目的话，使用二分查找，low是0，high是数字 x/2 + 1。我们需要查找一个数mid的平方小于等于x。因此，可以进行二分查找。需要注意的是返回的是high。

class Solution:
    def mySqrt(self, x: int) -> int:
        low = 0 
        high = int(x/2 + 1)
        while low <= high :
            mid = (low + high) // 2
            if mid ** 2 == x :
                return mid
            elif mid ** 2 > x :
                high = mid - 1
            elif mid ** 2 < x :
                low = mid + 1
        return high

还有一种方法是牛顿法, 利用一阶线性近似快速寻找最优点。

牛顿迭代法是用切线来估计曲线，我们可以在某个点上做切线得到切线方程y=f’(x0)(x-x0)+f(x0)，然后找出切线与横轴的交点，就是下一个迭代点。

迭代点和零点具体一个的关系：

牛顿法的公式具体推导：

最终得到：

比如求3的平方根，就是求曲线f(x)=x^2-3的零点，求导f’(x)=2*x，所以我们首先取x0=2，则x1 = 2 – 1 /4 = 1.75，然后x2 = 1.75 – [(1.75)^2 – 3]/(2*1.75) = 1.73214… 这个数就跟根号3很接近了。

class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        x0 = x
        x1 = x0/2 + x/(x0*2) 
        while abs(x0 - x1) >= 1:
            x0 = x1
            x1 = x1 / 2 + x / (x1 * 2)
        return int(x1)

有的时候，需要对平方根的误差进行估算，需要是小数点后6位，牛顿法瞬间解决。

def mySqrt(x: int) -> int:
    if x < 2:
        return x
    x0 = x
    x1 = x0 / 2 + x / (x0 * 2)
    while abs(x0 - x1) >= 0.000001:
        x0 = x1
        x1 = x1 / 2 + x / (x1 * 2)
    return x1

print(mySqrt(3))
# 1.7320508075688772

写作业（累加数组+二分查找的变形）

阿里云天池赛在线编程：在线编程限时赛。赛题链接：https://tianchi.aliyun.com/oj/9087601630820991/54270154473935464。此题为中等难度题目。

描述：n个人，他们每个人需要独立做m份作业。第i份作业需要花费cost[i]的时间。由于每个人的空闲时间不同，第i个人有val[i]的时间，这代表他做作业的总时间不会超过val[i]。每个人都按照顺序，从1号作业开始，然后做2号，3号...... 现在，你需要计算出他们最多花了多少的时间。

1<=n<=100000 1<=m<=100000 1<=val[i]<=100000 1<=cost[i]<=100000

示例
样例 1:

给定`cost=[1,2,3,5]`，`val=[6,10,4]`，返回`15`。
输入:
[1,2,3,5]
[6,10,4]
输出
15

解释:
第一个人可以完成1号作业，2号作业，3号作业，1+2+3<=6。
第二个人可以完成1号作业，2号作业，3号作业，无法完成4号作业，1+2+3<=10，1+2+3+5>10。
第三个人可以完成1号作业，2号作业，无法完成3号作业，1+2<=4，1+2+3>4。
1+2+3+1+2+3+1+2=15，返回15。

样例 2:


给定 `cost=[3,7,3,2,5]`,`val=[10,20,12,8,17,25]`,返回`78`.
输入:
[3,7,3,2,5]
[10,20,12,8,17,25]
输出:
78

解释:
第一个人可以完成1号作业，2号作业, 3 + 7<=10.
第二个人可以完成1号作业，2号作业，3号作业，4号作业和5号作业, 3+7+3+2+5<=20
第三个人可以完成1号作业，2号作业，无法完成三号作业,  3+7<=12,3+7+3>12.
第四个人可以完成1号作业，无法完成2号作业 , 3<=8,7+3>8.
第五个人可以完成1号作业，2号作业，3号作业，4号作业，无法完成5号作业,3+7+3+2<=17,3+7+3+2+5>17.
第六个人可以完成1号作业，2号作业，3号作业，4号作业和5号作业, 3+7+3+2+5<=25
3+7+3+7+3+2+5+3+7+3+3+7+3+2+3+7+3+2+5=78, 返回 78.

「这个题其实就是二分查找的变形，查找排序数组中，第一个大于目标值的前一个值或者等于目标值（数组中可能不存在目标值）」。这个排序数组就是cost的累加数组。

class Solution:
    """
    @param cost: the cost
    @param val: the val
    @return: the all cost
    """
    def doingHomework(self, cost, val):
        # Write your code here.
        sum = 0
        sums = []
        for i in cost:
            sum += i
            sums.append(sum)
        result = 0
        for n in val:
            if n != -1:
                result += binary_search(sums, n)
        return result

def binary_search(list, num):
    if num >= list[-1]:
        return list[-1]
    if num < list[0]:
        return 0
    left = 0
    right = len(list) - 1  # 注意1 low和high用于跟踪在其中查找的列表部分
    while left < right:
        mid = left + (right-left) // 2
        if list[mid] <= num and list[mid +1 ] > num:
            return list[mid]
        elif list[mid] > num  and list[mid-1] <= num:
            return list[mid -1 ]
        elif list[mid] < num:
            left = mid + 1
        else:
            right = mid -1
    return 0

「人生最重要的不是所站的位置，而是内心所朝的方向。只要我在每篇博文中写得自己体会，修炼身心；在每天的不断重复学习中，耐住寂寞，练就真功，不畏艰难，奋勇前行，不忘初心，砥砺前行，人生定会有所收获，不留遗憾 （作者：Runsen ）」

❝

本文已收录 GitHub，传送门~^[1] ，里面更有大厂面试完整考点，欢迎 Star。

❞

Reference