「@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 次計算。
那麼如果我們換一種思路來計算呢：
快速冪實際上是分治思想的一種應用。因此，可以得到：
下面就需要判斷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[1]傳送門~: https://github.com/MaoliRUNsen/runsenlearnpy100