是理論問題。
以leetcode為基礎的練習。
我的任務解決方案是二進制搜索。但問題不在于它。
我在討論選項卡上找到了完美的解決方案。
（下一個代碼已從那里獲取）
class Solution:
def mySqrt(self, x: int) -> int:
low, high= 1, x
while low<high:
high = (low high) // 2
low = x // high
return high
它作業完美。我的問題是：
對于常規的二分搜索，我們取序列中間，并根據比較結果洗掉多余的部分（左或右），然后重復直到結果。
這個實作基于什么？
該解決方案從一開始就在中間和小部分之后切割了部分序列。
uj5u.com熱心網友回復：
此代碼不是基于二進制搜索的。相反，它基于將古老的“巴比倫方法”應用于整數算術。反過來，這可以看作是對牛頓尋找方程根的更一般方法的一個實體。
在這段代碼中，保持不同low和high變數并不重要。例如，它更常見的編碼方式如下：
def intsqrt(n):
guess = n # must be >= true floor(sqrt(n))
while True:
newguess = (guess (n // guess)) // 2
if guess <= newguess:
return guess
guess = newguess
但要更加小心地找到更好的初始猜測。
順便說一句，二進制搜索每次迭代將“好位”的數量增加 1。這種方法大約使每次迭代的“好位”數量增加一倍，因此猜測越接近最終結果，效率越高。
uj5u.com熱心網友回復：
這種方法很微妙，盡管巴比倫人知道（見蒂姆的回答）。
假設h > √x. 然后
l = x/h < √x和(l h)/2 > √x.
第一個屬性是顯而易見的。對于第二個，觀察 1. 和 2. 暗示
x h2 > 2h√xor (h-√x)^2 > 0，這是真的。
所以h仍然在上面√x，但它越來越近（因為(l h)/2 < h）。而當計算是用整數進行的時候，就會有這樣的時刻l=h。
這種方法是如何發現的？
假設您有 的近似值h，√x我們希望通過修正來改進它δ。我們寫x = (h-δ)2 = h2-2hδ δ2 = x。如果我們疏忽了δ2，那么我們就畫h-δ = (h2 x)/2h = (h x/h)/2，這是我們的(h l)/2。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/422156.html
標籤：
上一篇：程式運行時背后的邏輯是什么？