爲什麼我的二進制搜索需要額外的比較？ log2（N）+1

Question

我想找到第一個整數在整數數組中的索引，它是< = key。我可以在log2（N）+1比較中使用二進制搜索。只有log2（N）比較纔有可能？

// Returns the index of the first integer in keys <= key. size must be a power of 2. 
unsigned find(int key, int* keys, unsigned size) {  
    int* origKeys = keys; 

    for (int i = 0; i < log2(size); i++) { 
     size /= 2; 

     if (keys[size] < key) 
      keys += size; 
    } 

    unsigned i = unsigned(keys - origKeys); 
    // Not only is this step messy, because it doesn't fit the loop, but 
    // now we have log2(n) + 1 comparisons. 
    if (*keys < key) 
     i++; 

    return i; 
} 

Answer 1

讓我們從信息論角度思考這個問題。如果你有一個有n個元素的數組，那麼新元素可以有n + 1個可能的點：在數組的任何元素之前，或者在所有元素之後。因此，您的算法需要進行足夠的比較，以便能夠唯一地識別哪個n + 1個點是正確的。如果你沒有做足夠的比較，你回報的答案並不總是正確的。

在最好的情況下，你做的每一次比較都可以消除一半可能的位置。因此，在理論極限中，通過k次比較，您可以決定2^k個位置中的哪一個是正確的。既然有n + 1個可能的位置，你需要在最壞的情況下進行lg（n + 1）比較，而不是lg n。由於你的n是兩個完美的力量，這意味着需要一個額外的比較。另一方面，如果你有一個小於2的完美冪，那麼讓ceil（lg n）比較就足夠了。

通過Eloff編輯，此代碼似乎給人以LOG2正確的答案（N + 1）的步驟，你預言：

// Returns the index of the first integer in keys <= key. size must be one less than a power of 2. 
unsigned find(int key, int* keys, unsigned size) {  
    int* origKeys = keys; 
    size++; 

    while(size > 1) { 
     size /= 2; 

     if (keys[size-1] < key) 
      keys += size; 
    } 

    return unsigned(keys - origKeys);   
}