無限遞歸：二進制搜索和斷言

Question

我正在寫一個二進制搜索的實現在C和我得到無限遞歸沒有明顯的（對我）的原因。我的繼承人代碼：

/*Orchestrate program*/ 
int main(int argc, char* argv){ 
    int array[] = {1,2,3,3,3,6,7,8,9,9,20,21,22}; 
    int length = 13; 
    int key = 23; 
    binary_search(key, array, 0, length - 1); 
    return 0; 
} 

int binary_search(int key, int array[], int first_index, int last_index){ 
    int middle; 
    middle = (first_index + last_index)/2; 
    if (first_index == last_index){ 
     if (array[middle] == key){ 
      printf("%d has been found at position %d\n", key, middle+1); 
     } 
     printf("item not found"); 
    } 
    else if (key > array[middle]){ 
     binary_search(key, array, middle, last_index); 
    } 
    else if (key < array[middle]){ 
     binary_search(key, array, first_index, middle); 
    } 
} 

根據我的主鍵的值，我想問題出在第一否則如果，但我不知道爲什麼。如果我要刪除first_index == last_index行，則該算法可以正常工作，但只能在該項目位於數組中時使用。如果該項目不在數組中，我自然會得到無限遞歸。

此外，我試圖通過刪除first_index == last_index行並將return -1;放在函數的末尾來解決此問題，但我遇到了與現在相同的問題。

編輯：

放在一起，我從幾個不同的用戶收到的諮詢件，我來到了以下解決方案（由一個錯誤和未嵌套的決定固定關斷）：

void binary_search(int key, int array[], int first_index, int last_index){ 
    int middle; 
    middle = (first_index + last_index)/2; 

    if (array[middle] == key){ 
     printf("%d has been found at position %d\n", key, middle+1); 
    } 
    if (first_index == last_index){ 
     printf("item not found"); 
    } 
    else if (key > array[middle]){ 
     binary_search(key, array, middle + 1, last_index); 
    } 
    else if (key < array[middle]){ 
     binary_search(key, array, first_index, middle - 1); 
    } 
} 

我有一個後續問題：有沒有辦法使用斷言來幫助我自己找到這個解決方案？ （我只是學習斷言所以我不知道我在哪裏可以應用它們）

Answer 1

你的功能應該是這樣的：

void binary_search(int key, int array[], int first_index, int last_index){ 
    int middle; 
    middle = (first_index + last_index)/2; 
    if (array[middle] == key){ 
     printf("%d has been found at position %d\n", key, middle+1); 
    } 
    else if (first_index == last_index) { 
     printf("item not found"); 
    } 
    else if (key > array[middle]){ 
     binary_search(key, array, middle + 1, last_index); 
    } 
    else { 
     //assert (key < array[middle]); // feel free to uncomment this one and include the assert library if you want 
     binary_search(key, array, first_index, middle - 1); 
    } 
} 

在遞歸調用換句話說，遞增或遞減中適當地。

這很重要，因爲，例如，當您將搜索縮小到2且中間是您的第一個元素時，則實際上您並未在遞歸調用中更改數組的維數。

我也將您的功能更改爲void，因爲您沒有返回任何內容。

Answer 2

您可以搜索排序數組的更小範圍。你的陣列的歡呼聲是包容性的。

遞歸的基本情況是：如果範圍爲空，則找不到密鑰。或者，在代碼中：

if (first_index > last_index){ 
    printf("Not found\n"); 
} 

只有在確定範圍不爲空時，才應該計算和比較範圍的中間元素。在這種情況下，你有三個結果：

• 中間元素是關鍵：賓果！
• 中間元素小於鍵：搜索數組的右半部分，並排除我們已經檢查過的中間元素。
• 中間元素大於關鍵字：同上，但與左半部分。

把所有這些組合起來：

void binary_search(int key, int array[], int first_index, int last_index) 
{ 
    if (first_index > last_index){ 
     printf("Not found\n"); 
    } else { 
     int middle = (first_index + last_index)/2; 

     if (array[middle] == key) printf("%d at index %d\n", key, middle); 

     if (key > array[middle]){ 
      binary_search(key, array, middle + 1, last_index); 
     } else { 
      binary_search(key, array, first_index, middle - 1); 
     } 
    } 
} 

此功能仍然有嘮叨我兩件事情：

• ，打印索引的功能是沒有什麼實際用處的。打印應該由客戶代碼完成，即由調用函數的代碼完成。相反，返回找到的索引或「找不到」的特殊值。
• 範圍包含邊界。這不是很像C。在C中，範圍通常由包含下限和唯一上限來描述。這就是數組索引和for循環的工作原理。遵循這個約定意味着您的客戶端代碼不必執行尷尬的計算。

所以這裏是一個返回指數或變體-1，如果關鍵不在數組中：

int binary_search1(int key, int array[], int first_index, int last_index) 
{ 
    if (first_index < last_index){ 
     int middle = (first_index + last_index)/2; 

     if (array[middle] == key) return middle; 

     if (key > array[middle]){ 
      return binary_search1(key, array, middle + 1, last_index); 
     } else { 
      return binary_search1(key, array, first_index, middle); 
     } 
    } 

    return -1; 
} 

，並對其進行測試：

int main() 
{ 
    int arr[6] = {3, 4, 6, 8, 12, 13}; 
    int i; 

    for (i = 0; i < 20; i++) { 
     int ix = binary_search(i, arr, 0, 6); 

     if (ix < 0) { 
      printf("%d not found.\n", i); 
     } else { 
      printf("%d at index %d.\n", i, ix); 
     } 
    } 

    return 0; 
} 

請注意，您的原始數組有重複的條目。這沒關係，但你會得到任何重複值的索引，不一定是第一個。