「@Author：Runsen」
❝编程的本质来源于算法，而算法的本质来源于数学，编程只不过将数学题进行代码化。「---- Runsen」 ❞
上次介绍了二分查找算法及其四个变形问题，下面介绍二分法常用的场景和典型的例题。
快速幂算法
题目是来自Leetcode：50. Pow(x, n)，https://leetcode-cn.com/problems/powx-n/
实现 pow(x, n) ，即计算 x 的 n 次幂函数。
代码语言：javascript复制示例 1:
输入: 2.00000, 10
输出: 1024.00000
其实快速幂相关的问题，个人觉得只要你是一名程序员，就必须要掌握快速幂算法。
当我们遇到一个问题需要让我们求得一个数 n 的 m 次方，那么最简单的方法是将 n 乘以 m 次，得到结果，但是如果我们现在需要计算的是 2^10000000 这样的式子呢，显然如果我们的程序需要计算 2 的更高次方的时候这样的算法，对于算法竞赛而言时间上显然是不允许的，因此提出了快速幂算法。
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取其相反数。
代码语言：javascript复制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 是非负整数。
代码语言：javascript复制# 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
# 示例 1:
# 输入: 4
# 输出: 2
# 示例 2:
# 输入: 8
#输出: 2
#说明: 8 的平方根是 2.82842...,
# 由于返回类型是整数，小数部分将被舍去。
二分查找的下界为 0
这个题目的话，使用二分查找，low是0，high是数字 x/2 1。我们需要查找一个数mid的平方小于等于x。因此，可以进行二分查找。需要注意的是返回的是high。
代码语言：javascript复制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位，牛顿法瞬间解决。
代码语言：javascript复制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的累加数组。
代码语言：javascript复制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
[1]传送门~: https://github.com/MaoliRUNsen/runsenlearnpy100
- END -
