C++:有15个数按又大到小顺序放在一个数组中,输入一个数,要求用折半法查找.......求每一步骤的解释.
发布网友
发布时间：2022-04-24 06:29
共3个回答
热心网友
时间：2023-10-08 20:58
折半查找法，是指在一组按顺序排列的数中，每次都从中间位置开始比较，如果等于被查找数就是找到了，如果不等于被查找数，则在另外一半的元素中找，循环往复，一直到找到或找遍为止。折半查找法最好的就是用函数的递归调用。
比如上题，要在一个15个元素的递增数组S中查找数值A，查找范围是S[0]－S[14]，那么首先是找出中间点S[7]作比较，如果S[7]等于A就是找到了，如果S[7]大于A，则说明A在S[0]－S[6]之间；反之，如果S[7]小于A，则说明A在S[8]－S[14]之间，然后再重复上述步骤，找出范围内的中间点进行比较，一直到找到或者不能再折半为止。
【程序代码】
#include <iostream> //控制台操作头文件
/*下面的Find()函数是在递增数组中用折半查找法的递归函数,其中S是要查找的数组,B是查找范围的起始下标,E是查找范围的终止下标,A是要查找的数值,如果找到了就返回该数值在数组中是第几个(从第0个开始算),如果找不到就返回-1*/
int Find(int *S,int B,int E,int A) //查找函数
{if(B>=E) //不能折半则无需继续递归
{if(S[B]==A) return B; //找到则返回数组下标
else return -1;} //找不到则返回-1
int I=B+(E-B+1)/2; //折半查找的中间点位置
if(S[I]==A) return I; //和中间点比较,找到则返回I
if(S[I]>A) E=I-1; //大于A则在数组的前半段查找
else B=I+1; //否则在数组的后半段查找
return Find(S,B,E,A);} //递归调用查找函数
int main() //主函数
{int S[]={1,3,5,7,9,11,13,15,17, //定义一个16个元素的递增数组
19,21,23,25,27,29,31,};
int A=0,O=0; //定义两个整型变量
while(A>=0) //当A为非负数的时候循环
{printf("请输入要找的数值:"); //显示提示输入的信息
scanf("%d",&A); //从键盘输出要查找的数
O=Find(S,0,15,A); //调用函数在S数组中查找
if(O==-1) printf("没有找到\n");//如果找不到显示提示信息
else printf("%d在第%d个\n",A,O);//否则显示出找到的对应下标
printf("\n");} //换行开始查找下一个
system("PAUSE"); //屏幕暂停,以便看到运行结果
return 0; //结束程序
}
【运行结果】
以上程序在DEV C++中运行通过，本来想附图，发现附不上来。
热心网友
时间：2023-10-08 20:59
#include <iostream>
using namespace std;
int binarySearch(int L[],int n,int x);
int main()
{
int x;
cout<<"请输入数组的值"<<endl;
int L[5];
for(int j=0;j<5;j++)
cin>>L[j];
cout<<"请输入需要查找的数字"<<endl;
cin>>x;
int t= binarySearch(L,5,x);
if(t<0)
{
cout<<"没有这个数的"<<endl;
}
else
cout<<"这个数是："<<t<<endl;
return 0;
}
int binarySearch(int L[],int n,int x)
{
int low=0;
int hign=n-1;
int mid;
while(low<=hign)
{
mid=(low+hign)/2;
if(L[mid]==x)
{
return x;
}
if(L[mid]>x)
low=low+1;
else
{
hign=mid-1;
return -1;
}
}
}
热心网友
时间：2023-10-08 20:59
追答。。。。。。算了，懒得写程序了。不好意思。
