//* * * * * * * * * * * * * * * * * * * * * * *
//CHAPTER      :6 (6-2)                       *
//PROGRAM NAME :二分查找                    *
//CONTENT      :查找                          *
//* * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#define MAX 30    //定義有序查找表的最大長度
typedef struct{
   char elem[MAX];       //有序查找表
   int length;             //length指示當前有序查找表的長度
}SSTable;
void initial(SSTable &);    //初始化有序查找表
int search(SSTable,int);        //在有序查找表中查找元素
void print(SSTable);             //顯示有序查找表中所有元素
void main()
{SSTable ST;      //ST為一有序查找表
 int ch,loc,flag=1;
 char j;
 textbackground(3);  //設置屏幕顏色
 textcolor(15);
 clrscr();
 //-------------------------程序解說-------------------------------------------
 printf("本程序演示對靜態表進行二分查找。\n");
 printf("首先輸入靜態表的元素個數。\n");
 printf("例如：5\n");
 printf("接著輸入各個元素（整形數）：\n例如：5 13 19 21 37\n");
 //----------------------------------------------------------------------------
 initial(ST);         //初始化有序查找表
 while(flag)
    { printf("請選擇：\n");
      printf("1.顯示所有元素\n");
      printf("2.查找一個元素\n");
      printf("3.退出\n");
      scanf(" %c",&j);
      switch(j)
	{case '1':print(ST); break; //顯示所有元素
	 case '2':{printf("請輸入要查找的元素：");
		   scanf("%d",&ch);      //輸入要查找的元素的關鍵字
		   loc=search(ST,ch);    //查找
		   if(loc!=0) printf("該元素所在位置是：%d\n",loc); //顯示該元素位置
		   else    printf("%d 不存在!\n",ch);//當前元素不存在
		   break;
		  }
	 default:flag=0;
	}
    }
 printf("程序運行結束!按任意鍵退出!\n");
}
void initial(SSTable &v)
{//初始化有序查找表
 int i;
 printf("請輸入靜態表的元素個數："); //輸入有序查找表初始化時的長度
 scanf("%d",&v.length);
 printf("請從小到大輸入%d個元素（整形數）：\n",v.length);
 getchar();
 for(i=1;i<=v.length;i++) scanf("%d",&v.elem[i]); //從下到大輸入有序查找表的各元素
}

int search(SSTable v,int ch)
{//在有序查找表中查找ch的位置，成功返回其位置，失敗返回0
 int low,high,mid;
 low=1;high=v.length; //置區間初值
 while(low<=high)
   {mid=(low+high)/2;
    if(v.elem[mid]==ch) return mid; //找到待查元素
    else if(v.elem[mid]>ch) high=mid-1; //繼續在前半區間進行查找
    else low=mid+1;                     //繼續在后半區間進行查找
 
   }
 return 0;     //找不到時，i為0
}
void print(SSTable v)          //顯示當前有序查找表所有元素
{int i;
 for(i=1;i<=v.length;i++) printf("%d ",v.elem[i]);
 printf("\n");
}