9.26.c

部分高校使用anyview编程测试数据结构习题,此代码为数据结构题集(c语言版)严蔚敏版的课后习题答案.专门提供给在anyview上运行,全部为通告代码

9.26②  试将折半查找算法改写成递归算法。
    
实现下列函数：
int BinSearch(SSTable s, int low, int high, KeyType k);
/* Index the element which key is k */
/* in StaticSearchTable s.          */
/* Return 0 if x is not found.      */

静态查找表的类型SSTable定义如下：
typedef struct { 
    KeyType key;  
    ... ...    // 其他数据域
} ElemType;

typedef struct {
    ElemType *elem;
    int       length;
} SSTable;
int BinSearch(SSTable s, int low, int high, KeyType k)
/* Index the element which key is k  */
/* in StaticSearchTable s.           */
/* Return 0 if x is not found.       */
{ 
  int mid;
  if(low>high) return 0;                             //查找不到时返回0
  mid=(low+high)/2;
  if(s.elem[mid].key==k) return mid;
  else if(s.elem[mid].key>k) return BinSearch(s,low,mid-1,k);
  else return BinSearch(s,mid+1,high,k);
  }