爲什麼我的二進制搜索實現不能找到最後一個元素？

Question

我已經在C語言中實現了二進制搜索的初始遞歸版本。但是，當要找到的元素位於數組的最後位置時，它似乎不起作用。有沒有辦法解決這個問題，而不改變函數的原型？

#include <stdio.h> 

int search(int value, int values[], int n); 

int main() { 
    int a[] = { 26, 27, 28 }; 

    if (search(28, a, 3) == 0) 
     printf("Found.\n"); 
    else 
     printf("Not found.\n"); 
} 

int search(int value, int values[], int n) 
{ 
    if (n <= 0) 
     return 1; 

    if (value < values[n/2]) 
     // Search the left half 
     return search(value, values, n/2); 
    else if (value > values[n/2]) 
     // Search the right half, excluding the middle term 
     return search(value, values + n/2 + 1, n/2 - 1); 
    else 
     return 0; 

    return 1; 
} 

Answer 1

你search功能是不正確的：

• 當你遞歸右側部分傳遞片尺寸的計算錯誤：它應該是n - n/2 - 1而不是n/2 - 1。

這裏是一個修正版本：

#include <stdio.h> 

int search(int value, int values[], int n); 

int main(void) { 
    int a[] = { 26, 27, 28 }; 

    if (search(28, a, 3) == 0) 
     printf("Found.\n"); 
    else 
     printf("Not found.\n"); 

    return 0; 
} 

int search(int value, int values[], int n) { 
    if (n > 0) { 
     int mid = n/2; 
     if (value < values[mid]) { 
      // Search the left half 
      return search(value, values, mid); 
     } else 
     if (value > values[mid]) { 
      // Search the right half, excluding the middle term 
      return search(value, values + mid + 1, n - mid - 1); 
     } else { 
      // Found the value 
      return 0; 
     } 
    } 
    return 1; 
} 

下面是一個簡單的迭代版本：

int search(int value, int values[], int n) { 
    while (n > 0) { 
     int mid = n/2; 
     if (value < values[mid]) { 
      // Search the left half 
      n = mid; 
     } else 
     if (value > values[mid]) { 
      // Search the right half, excluding the middle term 
      values += mid + 1; 
      n -= mid + 1; 
     } else { 
      // Found the value 
      return 0; 
     } 
    } 
    return 1; 
} 

Answer 2

它似乎是你的else if語句中的返回語句。數組n的長度應該是n-n/2-1而不是n/2-1否則最後一個元素將被刪除。隨着數組長度的增加以及您搜索來自右側的元素，您可以看到這種情況更爲普遍。

return search(value, values + n/2 + 1, n - n/2 - 1); 

注： 作爲chqrlie指出