9.26.c

来自「数据结构习题及答案」· C语言 代码 · 共 32 行

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);
  }