Question

这道数据结构编程题怎么做？将非递归的折半查找改写为递归算法，用C++编程，求大神解答~~~

Answer 1

没看到你的具体题目，折半算法对被查找的数组是有要求的，必须是顺序排列，而且递增和递减是不一样的。因为没看到具体要求，我只能按我的想法给你讲讲折半算法。
【解题思路】
　　折半查找法，是指在一组按顺序排列的数中，每次都从中间位置开始比较，如果等于被查找数就是找到了，如果不等于被查找数，则在另外一半的元素中找，循环往复，一直到找到或找遍为止。折半查找法最好的就是用函数的递归调用。
　　比如，要在一个15个元素的递增数组S中查找数值A，查找范围是S[0]－S[14]，那么首先是找出中间点S[7]作比较，如果S[7]等于A就是找到了，如果S[7]大于A，则说明A在S[0]－S[6]之间；反之，则说明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++中运行通过