一、算法思想

折半查找:又称“二分查找”,仅适用于有序的顺序表。
有序:要么递增、要么递减
顺序表:用数组来存放的。顺序表拥有随机访问的特性,链表没有。

  • 例子:

查找成功:
用low=0,high=TableLen-1 (第一个元素和最后一个元素)
mid=(low+high)/2
if(key > mid) low=mid+1;
else high=mid-1;
直到:high=low=key。能进行匹配

查找失败的:
用low=0,high=TableLen-1 (第一个元素和最后一个元素)
mid=(low+high)/2
if(key > mid) low=mid+1;
else high=mid-1;
直到:high =low =mid
下一步就是:low>high 或者 high<low 查找失败

二、算法实现

int Binary_Search(SSTable L,ElemType key){
	int low =0,high=L.TableLen-1,mid;
	while(high<low){
		mid=(low+high)/2;			//取中间位置。
		if(L.elem[mid]==key) 		//判断是否等于中间值。
			return mid;				//等于则返回索引值。
		else if(L.elem[mid]>key)   //如果key小于中间值,那么从前半部分找
			 high=mid-1;
		else low =mid +1;			//从后半部分查找
	}
	return -1;				  		//如果查找失败,返回-1
}
 

在这里插入图片描述

1、查找效率ASL

  • 绿色是:查找成功个数。
  • 紫色是:查找失败的个数。
    第一层只需要比较一次,个数为1
    第二层只需要比较二次,个数为2
    (第i层数第i层的个数 +第i层数第i层的个数)/ 总个数=平均查找效率ASL

查找成功ASL= (11 + 22 +43 + 44 )/11 = 3
在这里插入图片描述

在这里插入图片描述

三、查找判定树(重要)

一、特性:

1、折半查找的判定树:一定是平衡二叉树
2、折半查找的判定树:只有最下面一层是不满的,

3、
在这里插入图片描述4、左子树 < 中间结点 < 右子树结点
属于二叉排序树的定义、并且是平衡二叉排序树

5、n个成功结点的判定树、失败结点个数是:n+1个
n+1=成功结点的空链域数量
在这里插入图片描述

在这里插入图片描述

2、奇数个数据元素

在这里插入图片描述

  • 折半查找判定树的构造:
  • 奇数个数据元素:

顺序表当中总共有11个数据元素,奇数个元素
除了mid之外,还剩10个,偶数个元素。正好可以左右均匀分布。左右各5个
将左右从中间分割,第三个和第8个,是Mid之外,又可以分为左右各2个。

3、 偶数个数据元素:

  • 偶数个数据元素:

顺序表当中共有10个数据元素,偶数个元素
此时算的mid的值,【(0+9)/2=4】是4。
除了mid之外,只剩下奇数个元素,左半部分会比右半部分少一个元素。

在这里插入图片描述

在这里插入图片描述

四、折半查找效率

在这里插入图片描述
顺序查找效率是o(n)。
折半查找的效率并不是一定比顺序查找效率高。
比如要查找第一个元素,顺序第一次就可以找到,而折半查找就需要比较几次。
所以说,大部分情况下折半要比顺序好。


在这里插入图片描述

一、分块查找算法思想

用数组存放的数据,可以将一个数组中的数据,分为一小快索引表,例如小于10,小于20, 小于30…
可以将查找表,建立索引。
“索引表”中保存每个分块的最大关键字和分块存储空间
特点是:块内无序,块间有序
在这里插入图片描述

  • 例子:查找22
    1、先进行查找索引表,从第一个元素依次往后找。
    第一个元素10,小于22.
    第二个元素20,小于22.
    第三个元素30,大于等于22了,在这个区间内。
    2、如果22存在的话,肯定在30指向这个分块内。
    接下来就从这个分块的起始位置(就是块内元素索引的起始位置),依次与22进行比对。
    找到则返回…
    如果在块内最后一个索引位置没有匹配到(例如索引区间在6-8,已经到9了),说明查找失败。
  • 总结:
    1.在索引表中确定待查记录,所属分块(可顺序、可折半)
    2.在块内进行顺序查找。(由于块内是乱序)

二、查找效率分析(ASL)

最优的是:把n个元素,分为根号n块,每块,分为根号n个元素。
这样保证ASL最小的值。
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

Logo

汇聚原天河团队并行计算工程师、中科院计算所专家以及头部AI名企HPC专家,助力解决“卡脖子”问题

更多推荐