Question

C++:有15个数按又大到小顺序放在一个数组中,输入一个数,要求用折半法查找.......求每一步骤的解释.

Answer 1

【解题思路】
　　折半查找法，是指在一组按顺序排列的数中，每次都从中间位置开始比较，如果等于被查找数就是找到了，如果不等于被查找数，则在另外一半的元素中找，循环往复，一直到找到或找遍为止。折半查找法最好的就是用函数的递归调用。
　　比如上题，要在一个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++中运行通过，本来想附图，发现附不上来。

Answer 2

// Note:Your choice is C++ IDE
#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;
}
}
}

Answer 3

取出低（n+1）/2的数和你输入的数对比，如果你输入的数小的话到右边去查找，如果大的话到左边去查找。这个函数递归下去。如果相等的话返回索引。如果两次查到的都是同一个数的话就证明没有这个数，返回查找不到。

追问

程序后面注释解释,这么的不明白。.

追答

。。。。。。算了，懒得写程序了。不好意思。