求指出异常。在已经从小到大排序的数组中,输入一个数,用折半查找法求出该数是在数组的第几个数
求指出错误。在已经从小到大排序的数组中,输入一个数,用折半查找法求出该数是在数组的第几个数
#include <stdio.h>
#define n 10
int compare(int x,int y)
{
/* compare x and y,return -1 for less than,0 for equal,
1 for greater */
if (x < y) return -1;
else if (x == y) return 0;
else return 1;
}
int binsearch(int list[],int searchnum, int left, int right)
{
/*search list[0]<=list[1]<=...<=list[n-1] for searchnum.
Return its position if found.Otherwise return-1 */
int middle;
while(left<=right){
middle=(left+right)/2;
switch(compare(list[middle], searchnum)){
case -1:left = middle + 1;
break;
case 0: return middle;
case 1: right = middle-1;
}
}
return-1;
}
void main(void)
{
int list[n],i,x,y;
int searchnum,left,right;
printf("generate the new number:\n ");
scanf("%d%d%d\n",&searchnum,&left,&right);
for(i=left;i<right-left+1;i++)
scanf("%d\n",&list[i]);
scanf("%d%d\n",&x,&y);
compare(x,y);
binsearch(list,searchnum,left,right);
printf("\n answear:\n ");
}
------解决方案--------------------
#include <stdio.h>
#define n 10
int compare(int x,int y)
{
/* compare x and y,return -1 for less than,0 for equal,
1 for greater */
if (x < y) return -1;
else if (x == y) return 0;
else return 1;
}
int binsearch(int list[],int searchnum, int left, int right)
{
/*search list[0]<=list[1]<=...<=list[n-1] for searchnum.
Return its position if found.Otherwise return-1 */
int middle;
while(left<=right){
middle=(left+right)/2;
switch(compare(list[middle], searchnum)){
case -1:left = middle + 1;
break;
case 0: return middle;
case 1: right = middle-1;
}
}
return-1;
}
void main(void)
{
int list[n],i,x,y;
int searchnum,left,right;
printf("generate the new number:\n ");
scanf("%d%d%d\n",&searchnum,&left,&right);
for(i=left;i<right-left+1;i++)
scanf("%d\n",&list[i]);
scanf("%d%d\n",&x,&y);
compare(x,y);
binsearch(list,searchnum,left,right);
printf("\n answear:\n ");
}
------解决方案--------------------
- C/C++ code
#include <stdio.h> #define n 10 int compare(int x,int y) { /* compare x and y,return -1 for less than,0 for equal, 1 for greater */ if (x < y) return -1; else if (x == y) return 0; else return 1; } int binsearch(int list[],int searchnum, int left, int right) { /*search list[0]<=list[1]<=...<=list[n-1] for searchnum. Return its position if found.Otherwise return-1 */ int middle; while(left<=right){ middle=(left+right)/2; switch(compare(list[middle], searchnum)){ case -1:left = middle + 1; break; case 0: return middle; case 1: right = middle-1; } return binsearch(list, searchnum, left, right);// 递归 } return-1; } void main(void) { int list[n],i,x,y; int searchnum,left,right; printf("generate the new number:\n "); scanf("%d%d%d\n",&searchnum,&left,&right); for(i=left;i<right-left+1;i++) scanf("%d\n",&list[i]); //scanf("%d%d\n",&x,&y); //compare(x,y); int loc; loc = binsearch(list,searchnum,left,right); printf("\n answear: %d\n ", loc+1); }