我在一本書中看到過這種方法，用于進行二分查找，但無論我如何嘗試，我都無法理解它是如何作業的。有人可以向我解釋一下它是如何作業的嗎？
這本書的解釋沒有幫助：
這個想法是當我們接近目標元素時進行跳躍并減慢速度。變數 k 和 b 包含陣列中的位置和跳轉長度。如果陣列包含元素 x ，則搜索后 x 的位置將在變數 k 中。該演算法的時間復雜度為O(log n )，因為while回圈中的代碼對于每個跳轉長度最多執行兩次。
我不明白的是 k 在陣列中如何迭代？我們如何確保它不會跳過目標的索引？我嘗試使用樣本值跟蹤該程式的一些運行，但無法弄清楚 k 遵循的模式以查找目標 x 是否存在于陣列中。
int k = 1;
for (int b = n/2; b >= 1; b /= 2) {
while (k b <= n && t[k b] <= x) k = b;
}
if (t[k] == x) {} // x was found at index k
注意：我很清楚“常見的二分搜索演算法”（使用開始、中間和結束索引的演算法）
uj5u.com熱心網友回復：
b是您當前位置的跳躍長度。如您所見，b開始為n/2并且在每一步除以 2 直到達到 1。
現在，對于 each b，請記住b在 for 回圈中的每一步都除以 2，我們運行一個 while 回圈，在其中添加b到當前位置，即k。我們添加b了k對 2 個條件的檢查：k b小于n（以確保我們不會越界）和t[k b]小于x我們正在搜索的。
這實際上意味著，每一個b，我們添加b到k，直到它會超出我們正在尋找的價值。在這一點上，while 回圈中斷，我們分開b以更慢地接近目標，希望我們不要越過它。
finalb只是一個，以確保我們不會錯過x它是否只是位置之后的下一個元素k。
這樣看，一輛汽車正朝著一個目標疾馳。一開始汽車以最大速度行駛，當它接近目標時，它逐漸減速直到到達目標。
與傳統二分搜索的不同之處在于它有點反直覺，在傳統二分搜索中，我們遍歷目標，然后回傳并再次遍歷，在每次迭代中，我們減少來回執行的步驟。在這個演算法中，我們只前進（永遠不會超過目標），但我們通過除法不斷減少步長b。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/359137.html
上一篇：我如何在流程圖中顯示它？