#include "iostream.h"


#include <vector>
#include "time.h"
using namespace std;



template  <class Type>  class Item {
	public: 
		Item(Type value):key(value) {}
        Type getKey() {
			return key;
		}         //獲取關鍵碼值;
        void setKey(Type k){
			key=k;
		}
	private:
		Type  key;                           //關鍵碼域
		//...
		//其它域;                              //其它域
};

 



 template  <class Type>  int SeqSearch (vector<Item<Type>*>& datavector,int length, Type k)  {
    int i=length;
   datavector[0]->setKey (k);        //將第0個元素設為待檢索值
  while(datavector[i]->getKey()!=k)
	  i--;     //從后往前逐個比較
    return i;           //返回元素位置
}


 template  <class Type>  int SimpleSearch (vector<Item<Type>*>& datavector,int length, Type k)  {
    int i=length;
  
  while(datavector[i]->getKey()!=k&&i>0)
	  i--;     //從后往前逐個比較
    return i;           //返回元素位置
}


template  <class Type>  int BinSearch (vector<Item<Type>*>& datavector,int length,Type k)  {
   int low=1,high=length,mid;   //low, high分別記錄數組首尾位置
   while (low<=high){
	   mid=(low+high)/2;
	   if (k<datavector[mid]->getKey()) 
		   high = mid-1;               //右縮檢索區間
	   else if (k>datavector[mid]->getKey())
		   low = mid+1;           //左縮檢索區間
       else
		   return mid;                            //檢索成功，返回元素位置
   } 
	   return 0;                                 //檢索失敗，返回0
}


// 時間變量與時間函數
clock_t tstart = 0;  


void Settime()
  { 
	tstart = clock(); 
}


double Gettime()
  {
	return (double)((double)clock() - (double)tstart)/(double)CLOCKS_PER_SEC; 
}




main()
{ 
vector<Item<int>*> datavector(200001);
 	
Item<int>* darray[200001];

  for(int j=0;j<200001;j++)
  darray[j]=new Item<int>(j);
          
  vector<Item<int>*>::iterator outputIterator = datavector.begin();
  copy(darray, darray +200001, outputIterator);
 
  

	int k;




    Settime();//開始計時
      k= SeqSearch(datavector, datavector.size()-1,7);
    
	
	cout << "-->監視哨順序檢索耗時 : " ;
	cout << Gettime()<< endl ;
    


 
   Settime();//開始計時
      k= SimpleSearch(datavector, datavector.size()-1,7);
	cout << "-->一般順序檢索耗時 : " ;
   cout << Gettime()<< endl ;
  

    
return 0;   
}