【数据结构】查找— —线性表的查找(顺序查找、折半查找、分块查找)

一些概念：

• 查找：找到符合条件的数据元素。
• 查找表：有同一类型的数据元素组成。
• 动态查找表：在查找的同时对表做修改操作（如插入和删除），则相应的表称之为动态查找表，否则称之为静态查找表。
  动态查找表的表结构本身是在查找过程中动态生成的，即在创建表时，对于给定值，若表中存在其关键字等于给定值的记录，则查找成功返回；否则，插入关键字等于给定值的记录。
• 查找操作：增、删、检索、查询
• 关键字：唯一标识数据元素的数据项（例如你的身份证）
• 查找效率评价指标：ASL
  有查找成功、查找失败两种情况

1 顺序查找(Sequential Search)

1.1 思想

从表的一端开始，依次把给定关键值与记录的关键字进行比较，逐个检查关键字会否满足给定条件。

• 又叫线性查找，适用顺序存储 + 链式存储。
• 算法简单，对表结构无任何要求。可顺、可链、可有序、可无序
• 效率低、平均查找长度大。当 n 很大时，顺序查找就不礼貌了。

1.2 代码

//这里是 设置监视哨的顺序查找 版本
typedef struct{	//查找表的数据结构
	ElemType *elem;	//0号位置存哨兵，不用担心是否越界
	int TableLen;	//
}SSTable;

int Search_Seq(SSTable ST,ElemType key)
{
//在顺序表ST中查找关键字等于 key de数据元素。若找到，返回该元素在表中的值位置，否则 为0 
ST.elem[0]=key;	//哨兵
for(int i=ST.TableLen; ST.elem[i]!=key; — -i);	//从后往前找 当 i == 0时，循环一定会跳出
return i;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2 折半查找(Binary Search)

2.1 思想

首先将 key 与表中中间位置比较，若相等，则查找成功，返回该元素的存储位置；若不等，则在中间元素以外的前半部分或后半部分查找，然后缩小范围，重复，直至找到为止（在low所指分块中查找），或确定表中没有所需查找元素（low>high），查找失败，返回查找失败的信息。

• 又叫二分查找，顺序查找的优化，仅适用于关键字有序的顺序存储结构，表结构要求高。
• 效率提高了，折半查找每次查找比较都使查找范围缩小一半。
• 成功的折半查找恰好是走了一条从判定树的根到被查结点的路径，经比较的关键字个数恰好为该结点在树中的层次。
• 和快排有点像，快排循环的条件是low 这里循环的条件是low<=high，前后中三种情况。

2.2 过程

结合思想

• 折半查找判定树一定是一棵平衡的排序二叉树，时间性能O(log n)【⚠️与二叉排序树的时间性能有时不同】
• 比较次数不会超过树高
• 树高 h=向上取整(log (n+1)) （当有序序列有8个时，树高为4 ）
• 比较次数少，查找效率高，不适用元素常发生变动的线性表。

2.3 代码

//在有序表L中查找关键字等于key的数据元素。若找到，返回该元素在表中的位置，否则为0
int Binary_Search(SeqList L,ElemType key)
{
	int low=1,high=L.TableLen,mid;
	while(low<=high)
	{
		mid=(low+high)/2;	//取中间位置
		if(L.elem[mid]==key)
			return mid;		//找到了待查元素
		else if(L.elem[mid]>key)	//继续在前一子表进行查找
			high=mid-1;
		else	//继续在后一子表进行查找
			low=mid+1;
	}
	return 0;	查找失败，返回0
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3 分块查找(Blocking Search)

3.1 思想

• 又叫索引顺序查找，介于顺序查找和折半查找之间。
• 除表本身外，需建立一个索引表。索引表中每个分块的最大关键字和分块的起始地址。
• 特点：块内无序，顺序查找；块间有序，可顺序、可折半查找。
• 最终停在low所指的分块中，⚠️这里与折半插入不同，折半插入停在 high 所在位置
• 优：插入删除较容易，无需一定大量元素。适用于快速查找又经常动态变化的线性表。
• 缺：要增加一个存储空间并对初始索引表进行排序运算。
  

3.2 ASL

• ASL= (s*s + 2s +n) / (2s) =（n/s + s)/2 + 1
• 当 s= 根号(n) 时，ASL最小 = 根号(n+1)
  [具体证明过程可移步严蔚敏版数据结构分块查找部分]