//数据结构之二分法---适用于有序线性(顺序存储结构)表（其思想类似于在英语字典中查找一个单词）
#include<stdio.h>
void main()
{ 
   int half_search(int*,int,int);      //函数声明
   int t,count;
   int a[]={1,4,6,9,28,56,80,89,99,104,110,123,135,150};    //一个预设置的有序线性表，下面用二分法查找28的下标
   count=sizeof(a)/sizeof(int);      //获得数组中元素的个数    sizeof()返回对象所占用的字节大小
   //----------------------------------------------------------
   printf("please input the num you want to search:\n");
   scanf("%d",&t);                       //格式化输入
   t=half_search(a,count,t);   //在传递一个数组名到一个函数中时，它会完全退化为一个指针,也就是说
   //若定义  int *p=a, 则sizeof(p)=4,p是指向整型变量指针，sizeof 获得的是一个指针之所占的空间,应该是
   //长整型(long型)的，所以是4，这也就是为什么我们每次调用子函数处理数组时，都要指定数组的大小。

   if(t==-1) printf("\nsorry,no such num!\n");
   else         printf("\nok,the suffix is %d\n",t);
   return;
}
int  half_search(int *a,int count,int t)   //二分法查找
{
   int i,pre,next;
   pre=0;next=count-1;    //首尾赋值
   i=(pre+next)/2;                     //整除取中间
   if(t==a[0])        return 1;
   if(t==a[count-1])    return count;
   if(t>a[0]&&t<a[count-1] )
  while (1)
  {
    if(a[i]<t)
    {
    pre=i;
          if (i==next-1)  return -1;//当i和(pre或next)相邻时(即查找长度为0时)查找结束
       i=(next+i)/2;
    printf("up\t");
    }
       else if(a[i]>t)
    {
       next=i;
          if (i==pre+1)   return -1;
    i=(pre+i)/2;
    printf("down\t");
    }
       else return  i+1;
  }
   else return -1;
}