C语言中二分法查找问题
C语言中二分法查找 又叫折半查找， 其思路是对已经排好序的一组数找出中间的那个数，然后再作比较。但是如果给出的数是偶数个，那么中间的那个数怎么确定？？ 例如：1、 4、5、89、103、447，我要查找103，怎么办？
第1个回答 2013-11-18
就按这个例子来说吧left = 1 right =6 mid = (left+right)/2=3就是先比较103和5 103>5 left=mid+1=4 right = 6mid= (4+6)/2=5比较103 103 相等 退出
第2个回答 2013-11-18
#include <stdio.h>int number[6] = {1,4,5,89,103,447};int search(int num,int left,int right,int mid)
{
if(left == right && number[mid] != num){
return -1;
}
if(number[mid] == num){
return mid;
}
if(num > number[mid]){
return search(num,mid+1,right,(mid+right)/2);
}
else{
return search(num,left,mid-1,(left+mid)/2);
}
}int main()
{
int num;
int res;
int left = 0;
int right = (sizeof(number)/4);
int mid = (left+right)/2; printf("input the num you search:");
scanf("%d",&num);
getchar(); res = search(num,left,right,mid); if(res >= 0){
printf("the num postion at:number[%d]\n",res);
}else{
printf("the num you input isn't exist!\n");
} return 0;
}
{
if(left == right && number[mid] != num){
return -1;
}
if(number[mid] == num){
return mid;
}
if(num > number[mid]){
return search(num,mid+1,right,(mid+right)/2);
}
else{
return search(num,left,mid-1,(left+mid)/2);
}
}int main()
{
int num;
int res;
int left = 0;
int right = (sizeof(number)/4);
int mid = (left+right)/2; printf("input the num you search:");
scanf("%d",&num);
getchar(); res = search(num,left,right,mid); if(res >= 0){
printf("the num postion at:number[%d]\n",res);
}else{
printf("the num you input isn't exist!\n");
} return 0;
}
第3个回答 2013-11-18
偶数也没关系，(left+right)/2得到的还是个整数，就是中间两个元素左边那个……
相似回答
