折半查找法问题
程序员文章站
2024-03-20 18:28:34
...
1.问题描述
有15个数存放在一个数组中,输入一个数,要求用折半查找法找出该数是数组中第几个元素值。如果该数不在数组中,则打印出“无此数”。
2.编程分析
首先要把15个数排序,这里选择的是选择排序法,然后用折半查找法寻找此数num,这里需要定义三个变量分别是数组首部top,数组中部mid和数组尾部bot。即top=0,bot=14,mid=(top+bot)/2。然后利用循环结构while来寻找此数,循环条件是(top<=bot),如果a[mid]=num,则查找成功,输出该数在数组里的下标,如果a[mid]<num,则top=mid+1,如果a[mid]>num,则bot=mid-1。如果循环结束即top>bot,则输出“无此数”。
用C语言实现代码如下:
#include <stdio.h>
#include <stdlib.h>
int main()
{
int i,j,k,p,q,num,top=0,mid,bot=14;
int a[15];
for(i=0;i<15;i++)
scanf("%d",&a[i]);
for(i=0;i<15;i++)
{
p=i;
q=a[i];
for(j=i+1;j<15;j++)
{
if(q>a[j])
{
p=j;
q=a[j];
}
}
if(p!=i)
{
k=a[i];
a[i]=a[p];
a[p]=k;
}
printf("%d\t",a[i]);
}
printf("\n请输入要查找的数:");
scanf("%d",&num);
mid=(top+bot)/2;
while(top<=bot)
{
if(a[mid]==num)
break;
else
if(a[mid]>num)
bot=mid-1;
else
top=mid+1;
mid=(top+bot)/2;
}
if(top>bot)
printf("无此数\n");
else
printf("查找的数在数组的第%d个位置\n",mid+1);
system("pause");
return 0;
}
下一篇: SESSION