#include <stdio.h>
#define N 21
void main(void)
{
 int a[N];
 int i,n,num;
 int top,bottom,mid;
 int flag=1; //如果在表列中找到數字，則值為1，否則為0
 int loc=-1;//要查找的數在表列中的位置，如果loca=-1表示表列中沒有這個數;如果有這個數,則它的值為所在的位置

 printf("你想在多少個數中進行折半查找，請輸入（1--20）：");
 scanf("%d",&n);

 while(n<1 || n>20)
 {
  printf("你輸入的數不正確，請重新輸入。\n");
  printf("你想在多少個數中進行折半查找，請輸入（1--20）：");
  scanf("%d",&n);
 }

 printf("請你輸入一個整數 a[1]:");
 scanf("%d",&a[1]);

 i=2;
 while(i<=n)   //輸入從小到大的表列
 {
  printf("請你輸入一個整數 a[%d]:",i);
  scanf("%d",&a[i]);
  if(a[i] > a[i-1])
   i++;
  else
   printf("你輸入的數不滿足要求，請重新輸入。\n");
 }

 //輸出表列
 printf("\n輸出表列\n");
 for(i=1; i<=n; i++)
 {
  printf("%6d",a[i]);
 }
 printf("\n");

 printf("請你輸入要查找的數：");
 scanf("%d",&num);
 
 flag=1; //假設輸入的數在表列中

 top=n;
 bottom=1;
 mid=(top+bottom)/2;


 

 while(flag)  
 {
  printf("top=%d, bottom=%d, mid=%d, a[%d]=%d\n",top,bottom,mid,mid,a[mid]);
  if( (num>a[top]) || (num<a[bottom]) )  //輸入的數 num>a[top] 或者 num<a[bottom]，肯定num不在這個表列中
  {
   loc=-1;
   flag=0;
  }
  else if(a[mid]==num)  //如果num 等于找到的數
  {
   loc=mid;
   printf("找到數 %6d 的位置%2d\n",num,loc);
   break;
  }
  else if(a[mid]>num)  //若 a[mid]>num，則num 一定在 a[bottom]和a[mid-1]范圍之內
  {
   top=mid-1;
   mid=(top+bottom)/2;
  }
  else if(a[mid]<num) //若 a[mid]<num，則num 一定在 a[mid+1]和a[top]范圍之內
  {
   bottom=mid+1;
   mid=(top+bottom)/2;
  }
 }
 
 if(loc==-1)
 {
  printf("%d 這個數在表列中沒有找到。\n",num);
 }
printf("折半查找結束：");
 scanf("%d",&n);
}