当比较指针上的值而不是指针本身时，为什么二进制搜索函数不起作用

Question

我在c中创建了这个二进制搜索函数，但遇到了一个问题。我已经传递了一个排序数组的指针、它的(size-1(和要搜索的数字。当我尝试比较while循环中前一个位置和最后一个位置的值时，它不适用于中间元素右侧的值。例如，如果我为{1,2,3}传递一个数组＝{1,2,3,4,5}，则函数运行良好，但对于{4,5}，循环只运行一次并退出。还有一个问题，只有当我们比较指针地址上的值时，才会出现这个问题，但如果我比较指针，函数就会完美地工作。在下面给出的代码中进行更好的解释。

int binarysearch(int*p,int r,int num){
//p is pointer of an array, r is the (sizeof(array)-1), num is the number to be searched
int *mid;
while(*p<=*(p+r)){//if we replace the condition with(p<=(p+r)) the function works
mid=(p+(r/2));
printf("1 ");
if(*mid==num)
return *mid;
if(*mid<num)
p=mid+1;
else
r=((r/2)-1);  
}
return -1;
}

Answer 1

查看计算mid值的方法。

在第一次迭代中，mid=(p+(r/2))将正确地给出中间项。假设r=5，在第一次迭代中，我们得到了*mid<num，所以现在p=mid+1或p=p+3。现在的问题是r仍然是5，所以数组指针只是偏离了它的值，而没有标记新的结束。如果您稍后尝试使用结果地址，这很容易导致分段错误。

解决方案很简单：不要用指针和int来计算mid的位置。用两个指针来标记搜索有界符，或者用两个整数来标记它们的索引。您也可以使用您的方法，但请确保每次迭代都更新r大小。

第一个选项-使用索引(如果必须这样做，我可以选择(：

int binarysearch(int*p,int r,int num){
int mid;
int a=0;
while(a<=r) {
mid=(a+r)/2;
printf("1 ");
if(p[mid]==num)
return *mid;
else if(p[mid]<num)
a=mid+1;
else if(a==r)
break;
else
r=mid;
}
return -1;
}

第二种选择-你的固定版本：

int binarysearch(int*p,int r,int num){
int *mid;
while(r>=0) {
mid=p+(r/2);
printf("1 ");
if(*mid==num)
return *mid;
else if(*mid<num) {
p=mid+1;
r-=(r/2)+1;
}
else if (r==0)
break;
else
r/=2;
}
return -1;
}