• 二分法查找

    二分法查找

    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. }