b_search.c

《数据结构》教材源程序,可以让你轻松的根据教材学习数据结构

/***********************************************/
/*    二分查找算法      文件名：b_search.c     */
/*    函数名：binsearch1()、binsearch2()       */
/***********************************************/
#include "seqlist.h"

/*--------二分查找的非递归实现------*/
int binsearch1(seqlist l,datatype key)
{   int low=0,high=l.len-1,mid;
    while (low<=high)
       {  mid=(low+high)/2;                   /*二分*/
	  if (l.data[mid]==key) return mid;   /*检索成功返回*/
          if (l.data[mid]>key)
               high=mid-1;         /*继续在前半部分进行二分检索*/
          else low=mid+1;          /*继续在后半部分进行二分检索*/
       }
    return  -1;   /* 当low>high时表示查找区间为空，检索失败*/
}
    
/*--------二分查找的递归实现------*/
int binsearch2(seqlist l,datatype key,int low,int high)
{   int mid,k;
    if (low>high) return -1;                   /*检索不成功的出口条件*/
        else
        {  mid=(low+high)/2;                   /*二分*/
	   if (l.data[mid]==key) return mid;   /*检索成功返回*/
	   if (l.data[mid]>key)  return binsearch2(l,key,low,mid-1); /*递归地在前半部分检索*/
		  else return binsearch2(l,key,mid+1,high);          /*递归地在后半部分检索*/
        }  
              
}

/*   主函数   */
main()
{ int i,k;
  datatype key;
  seqlist l;
  printf("请输入线性表的长度:");
  scanf("%d",&l.len);
  for (i=0;i<l.len;i++)
     scanf("%d", &l.data[i]);
  printf("请输入待查找的关键字:");
  scanf("%d",&key);
  if ((k=binsearch1(l,key))!=-1)  printf("%d在线性表的第%d个位置。",key,k);
    else printf("未找到指定元素");
  if ((k=binsearch2(l,key,0,l.len-1))!=-1)  printf("%d在线性表的第%d个位置。",key,k);
    else printf("未找到指定元素");
}