二分法查找

  1. #include <stdio.h>
  2. #define MaxSize 100
  4. typedef int KeyType;
  6. typedef char ElemType[10];
  8. typedef struct
  9. {    
  10.     KeyType key;       /*存放关键字,KeyType为关键字类型*/
  11.     ElemType data;    /*其他数据, ElemType为其他数据的类型*/
  12. } LineList;
  14. int BinSearch(LineList R[],int n,KeyType k)
  15. {
  16.     int i,low=0,high=n-1,mid;
  17.     int find=0;                /*find=0表示未找到;find=1表示已找到*/
  18.        while (low<=high && !find)
  19.      {    mid=(low+high)/2;   /*整除取中间值*/
  20.         if (k<R[mid].key) 
  21.             high=mid-1;
  22.         else if (k>R[mid].key) 
  23.             low=mid+1;
  24.            else 
  25.         {    i=mid;
  26.             find=1;
  27.         }
  28. }
  29.      if (find==0) 
  30.         return(-1);
  31. else
  32.         return(i);
  33. }
  35. void main()
  36. {
  37.     KeyType a[]={2,4,7,9,10,14,18,26,32,40},k=7;
  38.     LineList R[MaxSize];
  39.     int n=10,i;
  40.     for (i=0;i<n;i++)
  41.         R[i].key=a[i];
  42.     i=BinSearch(R,n,k);
  43.     if (i>=0)
  44.         printf("R[%d].key=%d\n",i,k);
  45.     else
  46.         printf("%d不在a中\n",k);
  47. }