Question

有15个数按小到大的顺序存放在一个数组中,输入一个数,要求用折半查找法找出该数组中第几个元素的值.求解释

#include"math.h"
main()
{static int i,j,m,a[15]={1,4,9,13,21,34,55,89,144,233,377,570,671,703,812};
scanf("%d",&m);
for(j=0;j<15;j++)
printf("%4d",a[j]);
printf("\n");
i=7;
while(fabs(i-7)<8)
{if(m<a[7])
{if(a[i]-m==0)
{printf("it is at (%d)\n",i+1);break;}i--;}
else if(m>a[7])
{if(a[i]-m==0)
{printf("it is at (%d)\n",i+1);break;}i++;}
else
printf("8\n");
}
if(fabs(i-7)-8==0)
printf("There is not\n");
}

求解释， 谢谢了

Answer 1

比如给一个4的数，程序第一步从数组中取出排在中间数的数（i=7）,即 第8个数89.
用89和4比较。如果大于89就往后循环查找，即查找89后的{144,233,377,570,671,703,812}，
如果小于89就往前查找，即查找89前的]{1,4,9,13,21,34,55}，不管往前还是往后最大循环次数都是7，所以while循环结束条件是（fabs(i-7)<8），即最大执行7次。
其实这个程序就第一步查找是二分法。不算严格的二分。严格二分应该之后都是像第一次查找那样从中间开始取个值出来比较然后决定下一步的循环方向。

Answer 2

输入89的时候好象有问题，无限循环了。。。应该在printf("8\n");后面加给break;

Answer 3

#include
void main()
{
int a[16],i,t,j;
printf("please input 15 numbers :\n");
for(j=1;j<16;j++)
scanf("%d",&a[j]);
printf("\n");
for(j=1;j<16;j++)
for(i=j+1;i<16;i++)
if (a[j]<a[i])
{
t=a[j];
a[j]=a[i];
a[i]=t;
}
puts("Please input the number to be found");
scanf("%d",&t);
putchar('\n');
i=1;
j=15;
//i,j表示在在数组a的第i个到第j个元素的范围内查找t
while (i<j)//i==j表明t只有可能是数组a的第i个元素
{
if (t<=a[(i+j)/2]) j=(i+j)/2;//此时t在第i个到第(i+j)/2个元素的范围内
else i=(i+j)/2+1;//此时t在第(i+j)/2+1个到第j个元素的范围内
}
if (a[i]!=t) puts("No such element!");//没找到
else printf("%d is element %d of the array.\n",t,i);//找到了
}