a.cpp

递归实现折半查找的C＋＋源程序,快速查找一个数在数列中位置.

// a.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream.h>
//递归实现折半查找
template <class T>

int BinSearch(T A[],int low,int high,T key)
{
   int mid;
   T midvalue;
   if (low>high)
    return -1;
   else
   {
    mid=(low+high)/2;
    midvalue=A[mid];
    if (midvalue==key)
     return mid;
    else if (midvalue < key)  //上半区
     return BinSearch(A,mid+1,high,key);
    else
     return BinSearch(A,low,mid-1,key);
   }
} 

void main()
{
 int A[10]={2,5,8,10,15,18,20,35,50,70};
 int i,key,pos;
 for(i=0;i<10;i++)
  cout<<A[i]<<"  ";
 cout<<endl<<"Input a number:";
 cin>>key;
    cout<<endl;
 pos=BinSearch(A,0,9,key);
 if (pos!=-1)
  cout<<"The position is "<<pos<<endl;
 else
  cout<<"Not exist."<<endl;

}