我剛剛開始學習一些基本演算法，但有一些關于二分搜索演算法的東西讓我感到困惑。
據我所知，二分搜索的最大時間復雜度是 O(log(n))，其中 log 是基數 2。
但是，當對不是 2 的冪的 N 值使用公式時，您會得到一個非整數值。
我感到困惑的是，如果你最終得到，比如說 3.3，是最多 3 步或 4 步。
使用 n = 10 的陣列時，您會得到值 3.3。話雖如此，我手動計算了步數，結果為 4，所以我假設您將四舍五入。
但是在我的教科書中，它說 n=10000 的陣列最多需要 13 步。當把它放在上面的對數公式中時，我們得到 13.2，這意味著在這種情況下我們向下取整。
我嘗試過對不同大小的陣列進行二分搜索，我得到了必須四舍五入才能獲得教科書答案的實體，以及必須四舍五入的實體。
我不確定什么時候向上或向下取整，或者我是否完全犯了另一個錯誤。
如果有人給我舉個例子，你能不能使用一個大小為 100000 的陣列。因為在書中它說最多 16 次，但是當我手動將 100000 減半直到我得到 1 時，我得到了 17 次。
提前致謝！
uj5u.com熱心網友回復：
最壞情況的公式是
換句話說，您加一并向下取整。見https://en.wikipedia.org/wiki/Binary_search_algorithm#Performance
但是在我的教科書中，它說 n=10000 的陣列最多需要 13 步。
你的課本錯了。正如您所期望的那樣，對具有 10000 個元素的陣列進行二分搜索最多需要 14 個步驟。
在每一步，陣列大小將減少 2 倍。所以步長將是 10000、5000、2500、1250、625、312、156、78、39、19、9、4、2、1。就像你一樣可以看到，那是14步。
因為在書中它說最多 16 次，但是當我手動減半 100000 直到我得到 1 時，我得到了 17 次
你是對的，書是錯的。
uj5u.com熱心網友回復：
我們用10的小例子，先學走路再跑。假設陣列是 [2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000] 并且我們正在搜索 3000。
- 剩下 10 個元素。比較 50. 向右走。
- 還剩 5 個元素。比較 500。向右走。
- 還剩2個元素。比較 1000。向右走。
- 保留 1 個元素。比較 2000。向右走（或決定“未找到”）。
那是4個比較。所以，是的，您可以進行匯總，因為您不能免費執行“部分步驟”，但有時您很幸運并且步驟較少，如在上面的示例中，如果您搜索 1，則只需進行 3 次比較（50， 5, 2) 假設將偶數長度組的索引向左四舍五入。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/400685.html
上一篇：使用堆演算法生成排列
下一篇：乘法后計算溢位位的有效方法