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

/*
查找：静态查找、动态查找、哈希查找
查找方式：静态查找，动态查找
方法：关键字查找，索引表查找
 *折半查找有递归和非递归两种算法，递归的特点是实现简单
 *非递归实现复杂，但是算法时间效率高
 *折半查找建立在排好序的基础上
 */
#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
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
flag=0;
for(j=0;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
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
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;
}