關於c中的二進制搜索算法的問題

Question

我在搜索數組中不存在的元素時低估代碼的行爲時感到困惑。

1. 我正在查找的元素索引的結果始終爲零，同時聲明它爲int index;。
2. 我正在尋找的元素索引的結果是隨機數，同時聲明它爲size_t index; 在下面的代碼中聲明變量索引爲int index;和size_t;有什麼區別。

代碼

#include <stdio.h> 
#define SIZE 5 
int main(void) 
{ 
    int numbers[SIZE]={1,2,3,4,5}; 
    int search =0; // This variable define the required number i am searching for 
    int start = 0 ; 
    int end = SIZE-1 ; 
    size_t index; 
    while (start <= end) 
    { 
     int middle = (start+end)/2; 
     if (search == numbers[middle]) 
     { 
      index = middle; 
     } 
     if (search > numbers[middle]) 
     { 
      start = middle+1 ; 
     } 
     else 
     { 
      end= middle-1 ; 
     } 
    } 
    printf("The index of the element is %d",index); 
return 0; 
} 

Answer 1

的基本問題是，index沒有初始化，當你沒有找到你正在尋找什麼它從來沒有得到分配。由於printf語句在這種情況下訪問未初始化的變量，因此您的代碼具有未定義的行爲，即可能發生任何事情 - 包括打印各種數字。

我正在尋找的元素索引的結果在聲明爲int索引時總是爲零;

這就是「只是運氣」

我期待的元素索引的結果是同時宣告它作爲爲size_t指數隨機數;

這也是「只是運氣」

Answer 2

您未使用正確的說明符的size_t，它不是％d。

嘗試使用％zd或％ld，它會正常工作。

此外，在while循環後面添加它，以便在元素不存在於數組中時不會顯示索引的奇怪值。

if(start>end) { 
    printf("That number is not present in the array"); 
    return 0; 
} 

然後，條件if (search == numbers[middle])下，招行printf("The index of the element is %d",index);。所以即使它存在於數組中，也不會得到「這個數字不存在」。 爲了您的代碼中看到https://code.hackerearth.com/80043dg?key=7b325b26aec0f5425b76cc3efbdc93cf

Answer 3

這裏的修正版本，是一對夫婦的行動項目，你可以用來提高你的代碼：由於這陣定義是靜態的，沒有必要列入SIZE定義裏面

1. []。聲明它是這樣的int numbers[]={1,2,3,4,5};而不是這個int numbers[SIZE]={1,2,3,4,5};。讓編譯器爲你做數學。
2. 將index初始化爲某個值（即index = 0;）。這是問題的主要原因，它向程序引入了未定義的行爲。
3. 將size_t index的類型更改爲int index程序中聲明的每個變量都是int，程序將index視爲int。所以它可能是一個int以避免混淆。

4. 使這是一個else if條款，而不是僅僅一個if：如果要搜索的值是從數據集中缺少

   else if (search > numbers[middle]) 
   { 
       start = middle+1 ; 
   } 
   

5. 添加另一種情況，使程序正常失敗。比如，printf("Data not found: %d", search);

的算法還不是100％，並有一些瑕疵，但我會離開這個由你來弄清楚。我希望這個信息有幫助！

最好的問候！

Answer 4

問題是，index的值未初始化。

將變量初始化爲0並不能解決您的問題。 因爲您正在使用index來返回數組元素的位置。

通過初始化index = 0將爲數組中不存在的元素以及數組的第一個元素提供相同的結果。

的更好的方法是作爲初始化size_t index = -1;

使得用於所述陣列中不存在的元素的結果將b -1。

另請檢查printf語句中使用的訪問說明符，以獲取size_t數據類型。它可以是，

printf("The index of the element is %ld",index);