我試圖弄清楚如果給定一個陣列，該陣列在以 2 為基數“記錄”時的長度不會產生整數，則二進制搜索必須執行多少操作。
我真的不知道該怎么辦。
uj5u.com熱心網友回復：
上限為上一個整數。不能做“0.2”的運算，是一還是零，還需要做“更多的事情”……所以是一個整體的運算。
對于 5 個元素的陣列，您的二進制搜索是（最壞情況）：
(O = non tested, - = rejected, X = value to search)
X O O O O
^ Start here. Op. #1
X O - - -
^ New pivot Op. #2
X - - - -
^ Found Op. #3
如您所見，您獲得的運算元量與 8 個元素的最壞情況完全相同，即 2 的下一個冪。并且log2(5)=2.32...，上限為 3，這也是最壞的情況。
uj5u.com熱心網友回復：
二分查找有三種情況：pivot 匹配，它太大，或者它太小。如果您的串列長度為 n，并且樞軸位于索引 floor(n/2)，則新問題的大小為 0，floor((n-1)/2)，ceil((n-1)/2)。
最壞的情況是您每次都選擇 ceil((n-1)/2) 情況。這給出了大小為 n 的串列的最壞情況比較次數的遞回關系：
C(0) = 0
C(n) = 1 C(ceil((n-1)/2)) = 1 C(floor(n/2))
稍微思考一下，C(n) 是 n 的二進制長度，對于 n>0，它是 floor(log_2(n)) 1。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/452511.html