关于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);