如何用c语言实现折半查找

hello大家好！我依然是你们熟悉的槿凉。那么最近呢由于学校里面的事情比较多，就没有来得及更新博客，不知道小伙伴们有没有想我啦！哈哈哈哈哈哈哈哈哈哈啊哈哈哈哈！ 好了，废话不多说，今天我们将来说一说这个折半查找的含义以及具体使用方法。

首先，我们来认识一下什么是折半查找？

定义：折半查找属于二分法里面的一种查找的方法，折半查找又称为二分查找，是一种高效率的查找方法。

要求：折半查找要求所查找的序列是有序的，为了简单，假设该序列是递增的。

思路：设a[low……high]是当前查找区间，首先确定该区间的中间位置mid=（low+high）/2;然后将待查的kz值与a[mid].key相比较。

1>若k==a[mid].key,则查找成功并返回该元素的下标。

2>若k<a[mid]，则由表的有序性可知，则该元素必定位于左之表，故新的查找区间是左之表a[low……mid-1]。

3>若k>a[mid]，则由表的有序性可知，则该元素必定位于右之表，故新的查找区间是右之表a[mid+1……high]。

下一次查找是针对新的查找区间进行的。

下面看一下完整的代码段：

#include<stdio.h>
int BinSearch(int a[],int low,int high,int k)
{
	int mid;
	if(low<high)//当前区间存在元素时 
	{
		mid=(low+high)/2;//求查找区间的中间位置 
		if(a[mid]==k)
			return mid;//找到后返回其物理下标 
		if(a[mid]>k)
			return BinSearch(a,low,mid-1,k);//当a[mid]>k时，在a[low……mid-1]序列中查找 
		else
			return BinSearch(a,mid+1,high,k);//当a[mid]<k时在a[mid+1……high]序列中查找 
	}
	else return -1;//当前查找区间没有元素时返回-1 
 } 
 int main()
 {
 	int n=10,i;
 	int k=6;
 	int a[]={1,2,3,4,5,6,7,8,9,10};
 	i=BinSearch(a,0,n-1,k);
 	if(i>=0)
 	printf("a[%d]=%dn",i,k);
	 else printf("未找到%d元素n",k); 		
 } 

 这里我们查找的元素下标是6，即a[5]，下面看一下运行结果：

最后

以上就是义气鞋子为你收集整理的如何用c语言实现折半查找的全部内容，希望文章能够帮你解决如何用c语言实现折半查找所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。