#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

typedef int keyType;

typedef int ElemType;

typedef struct{
  ElemType *elem;
  int length; 
}SSTable;

int Create(SSTable &ST,int n){
  int i;
  int x=0;

  ST.elem=(ElemType*)malloc((n+1)*sizeof(ElemType));
  printf("請輸入9個數:");
  for(i=1;i<=n;i++){
	  scanf("%d",&x);
    ST.elem[i]=x;
  }
  ST.length=n;
  return 1;
}

int Search_Seq(SSTable ST,keyType key){
   int i;
   ST.elem[0]=key;
   for(i=ST.length;ST.elem[i]!=key;--i);
   
   return i;
}


int Search_Bin(SSTable ST,keyType key){
    ElemType low,high,mid;
    low=1;high=ST.length;
    while(low<=high){
       mid=(low+high)/2;
       if (key==ST.elem[mid]) return mid;
       else if (key<ST.elem[mid]) high=mid-1;
       else low=mid+1;
    }
    return 0;
}


main(){
   
   SSTable ST;
   int i;
   Create(ST,9);  //9個數
   
   i=Search_Seq(ST,5);
   printf("5是序列中的第%d個\n",i);

   i=Search_Bin(ST,7);
   printf("7是序列中的第%d個\n",i);
   
   return 1;
}