//File : main.cpp
//Designer : Ma Zhejiang  (from the class KT323-1)
//Data :  3/11/2005
//Subject:二分查找方法

#include "iostream.h"

template <class Type>
int Find(Type * pDatas,int nCount,Type & Data)
//Find a item Data from a group datas pointed by the pointer pDatas.
//從一組被指針 pDatas 指向的數(shù)據(jù)中查找某個(gè)數(shù)據(jù)
//The group datas must be ordinal from small to big.
//這組數(shù)據(jù)必須是有序的
//The nCount means how many items exist in the group datas.
//nCount 是這組數(shù)據(jù)的個(gè)數(shù)
//If the group datas exit the item, return the number of its order,
//or give a integer zero
//如果這組數(shù)據(jù)中存在數(shù)據(jù)data，函數(shù)就返回這個(gè)數(shù)的序數(shù)，
//否則就返回零值
{
   int small=0,big=nCount-1;
   int mid=(big+small)/2;
   while(big>=small)
   {   
	  if(*(pDatas+mid)==Data)
		 return mid+1;
	  else if(*(pDatas+mid)<Data)
		  small=mid+1;
	  else
		  big=mid-1;
	  mid=(big+small)/2;
   }
   return 0;
}

void main()
{
	int number[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
	int count=20;
	int findData,findPosition;
	char choose;
	cout<<"A group of ordinal datas are the following numbers."<<endl;
	cout<<"一組有序的數(shù)據(jù)如下："<<endl;
	for(int i=0;i<count;i++)
	   cout<<number[i]<<" ";
	cout<<endl;
	while(1)
	{
	   cout<<"Please input the data that you want to find. "<<endl;
       cout<<"請(qǐng)輸入你想要查找的數(shù)據(jù)：";
	   cin>>findData;
	   if(findPosition=Find(number,count,findData))
	   {
		   cout<<"The data "<<findData<<" is found . The number is the "<<findPosition<<"th."<<endl;
           cout<<"數(shù)據(jù)"<<findData<<"被找到。序數(shù)是第"<<findPosition<<"個(gè)。"<<endl; 	   
	   }
	   else
	   {
	      cout<<"The data "<<findData<<" isn't found in the group datas."<<endl;
	       cout<<"在這組數(shù)據(jù)中找不到數(shù)據(jù)"<<findData<<"。"<<endl;  
	   }
	   cout<<"Do you want to continue to test?Yes/No (Y/N) :"<<endl;
	   cout<<"你想繼續(xù)測(cè)試嗎？是/否（Y/N）：";
	   cin>>choose;
	   if(!(choose=='y'||choose=='Y'))
	       break;
	}
}