首页 > 代码库 > 查找总结(一)-----简单查找和折半查找

查找总结(一)-----简单查找和折半查找

先介绍一个概念,平均查找长度(ASL)为每一个关键字出现的概率*查找该关键所进行比较的次数,所有关键字这样的值之和

 

一.简单查找

    简单查找,也就是一个个地比较了,不多说

int Easy_find(char c[],int n,char key)
{
	int i=0;
	while (i<n&&c[i]!=key)
	{
		i++;
	}
	if (i<n)
	{
		return i;
	}
	else
	{
		return NO_FIND;
	}
}

    时间复杂度分析:while循环最少比较1次,最多比较n次,所以时间复杂度为O(n),另外,平均查找长度为(1+2+....n)*n/2/n=n+1/2;总之,平均查找长度也为O(n),当然,这是在假设每个关键字的概率相同

 

 

 

 

折半查找

  所谓折半查找,还是借鉴了折半的思想,通过这种方式减少比较的次数,和插入类排序中减少寻找插入位置的时间是一样的,不多说,下面是折半插入的代码

#define NO_FIND -1

//注意! 折半查找需满足两个重要条件:1.元素本来是有序的2.元素必须采用顺序结构...实际上凡是遇到折半的思想,基本都要蛮子这两个条件
int Half_find(char a[],int n,char key)
{
	int low=0;
	int high=n-1;
	while (low<=high)
	{
		int mid=(low+high)/2;
		if (key==a[mid])
		{
			return mid;
		}
		else if (key>a[mid])
		{
			low=mid+1;
		}
		else if (key<a[mid])
		{
			high=mid-1;
		}
	}
	return NO_FIND;

}

  

 

要注意两点:

      1.折半查找只适用于顺序存储结构

      2.折半查找要求关键字事先是有序的

  顺便总结一下:事实上凡是用到了折半思路的算法基本上都有这两个要求,折半插入排序因为自身的原因,在寻找插入位置的时候,事先肯定是有序的

 

算法分析:

  折半查找比较的次数可用二叉判定树来判断,注意!,二叉判定树并不是二叉排序树,百度搜索排名第一的那个博客瞎jb说,真是误人子弟,二叉判定树根本就不是一颗完全二叉树,但是他的深度和相同结点数目的完全二叉树是一样的,就是|log2(n)|+1(注:这里两条竖线,是取下值的意思,)

 

因此,折半查找的比较次数最少为1次,也就是只比较根节点,最多为|log2(n)|+1次,时间复杂度为O(log2(n))平均查找长度也是O(log2(n))级别的,具体值大约为log2(n+1)-1;

 

 

 

分块查找法:

    思路:

        将关键字分为若干块,块有以下特点

          1.块间有序:块间的排序用块内关键字的最大值比较而得

          2.块内无序

    步骤:首先,用折半查找来确定所查关键字所处的块

        然后,在块内用简单查找

 

查找总结(一)-----简单查找和折半查找