分别用递归和循环简单实现折半查找

作者:ygfinsight 和c/c++相关  
/*
查找:静态查找、动态查找、哈希查找
查找方式:静态查找,动态查找
方法:关键字查找,索引表查找
 *折半查找有递归和非递归两种算法,递归的特点是实现简单
 *非递归实现复杂,但是算法时间效率高
 *折半查找建立在排好序的基础上
 */
#include
#include


typedef int key_type;
typedef struct data_type {
key_type key;


}data_type;


void Print(data_type a[],int n)
{
int i;
for(i=0;i<n;i++){
printf("%d ",a[i].key);
}
printf("\n");
}
void bubble_sort(data_type a[],int n)
{
int i,j,flag=1;
data_type temp;
for(i=1;i<n&&flag==1;i++){
flag=0;
for(j=0;j<n-i;j++){
if(a[j].key>a[j+1].key){
flag=1;
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;

}
}

}
}
//用递归方法实现折半查找
int binary_search_recursive(data_type a[],data_type x,int low,int high)
{
int mid;
if(low>high) return -1;
mid=(low+high)/2;
if(x.key==a[mid].key) return mid;
else if(x.key<a[mid].key) binary_search_recursive(a,x,low,mid-1);
else return binary_search_recursive(a,x,mid+1,high);
}
//用循环实现
int binary_search(data_type a[],data_type x,int low,int high)
{
int mid;
while(low<=high)//用循环代替递归
{
mid=(low+high)/2;
if(x.key==a[mid].key) return mid;
else if(x.key<a[mid].key) high=mid-1;
else if(x.key>a[mid].key) low=mid+1;


}
return -1;
}
int main()
{
data_type array[10]={0,9,6,7,8,5,3,4,2,1};
bubble_sort(array,10);
Print(array,10);
printf("查找成功,9元素位于%d位置。\n",binary_search_recursive(array,array[9],0,9));
printf("查找成功,9元素位于%d位置。\n",binary_search(array,array[9],0,9));
return 0;
}

相关资料:

分别用递归和循环简单实现折半查找来源网络,如有侵权请告知,即处理!

编程Tags: