[数据结构与算法]数据结构---折半查找算法代码

1.折半查找又称二分查找，它仅适用于有序的顺序表（注：折半查找不适合链表，因为顺序表拥有随机访问的特性，而链表没有）。

2.折半查找可以采用非递归算法，也可以采用递归算法。下面就用代码分别实现两种算法:

//非递归算法实现
#define maxSzize 10000;
typedef struct seqList
{
   int data[maxSzize];
   int length;
};
int midSearch(seqList L,int key)
{
   int low=0,mid,high=L.length-1;//折半查找中的三个指针
   while(low<=high)//当low指针小于等于high指针时，执行循环
   {
      mid=(low+high)/2;//初始化mid指针
      if(L.data[mid]==key)//当要查找的元素等于mid指向的元素时，此时查找成功，直接返回数组下标
      {
         return mid;
      }else if(L.data[mid]>key){  //向前半部分查找
         high=mid-1;
      }else{         //向后半部分查找
         low=mid+1;
      }
   }
   return 0;
}

//递归算法实现
#define maxSzize 10000;
typedef struct seqList
{
   int data[maxSzize];
   int length;
};
int midSearch(seqList L,int key,int low,int high)
{
   if(low>high)//递归出口，当low指针大于high指针时，说明查找失败，从而结束递归
   {
      return 0;
   }
   if(key>L.data[mid])
   {
      midSearch(L,key,mid+1,high);//向后半部分查找
   }else if(key<L.data[mid])
   {
      midSearch(L,key,low,mid-1);//向前半部分查找
   }else{ //此时对应情况为：L.data[mid]==key;
      return mid;
   }
}