经典查找算法

查找 —— 在数据集合中寻找满足某种条件的数据元素的过程

查找表（查找结构）—— 用于查找的数据集合称为查找表，它由同一类型的数据元素组成

关键字 —— 数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

评价指标：

查找长度 —— 在查找运算中，需要对比关键字的次数

平均查找长度 —— 所有查找过程中进行关键字的比较次数的平均值

顺序查找

算法思想：从头到尾挨个找，适用于顺序表、链表。

$AS{L}_{查找成功}=\frac{n+1}{2}$，$AS{L}_{查找失败}=n+1$

顺序查找的优化（对有序表）：查找表中元素有序存放

$AS{L}_{查找失败}=\frac{n}{2}+\frac{n}{n+1}$

用查找判定树分析ASL：

一个成功结点的查找长度 = 自身所在层数

一个失败结点的查找长度 = 其父节点所在层数

折半查找

算法思想：二分查找，只适用于有序的顺序表
算法实现：

#include 
#include 

using namespace std;

int BinarySearch(vector<int>& L, int key) {
	int low = 0, high = L.size() - 1, mid;
	while (low <= high) {
		mid = (low + high) / 2;
		if (L[mid] < key) low = mid + 1;
		else if (L[mid] > key) high = mid - 1;
		else return mid;
	}
	return -1;
}

int main()
{
	vector<int> num = { 1, 2, 4, 6, 7, 9, 10 };

	int loc = BinarySearch(num, 7);

	cout << loc << endl;

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

查找效率分析

分块查找

分块查找，又称索引顺序查找，算法过程如下：

1. 在索引表中确定待查记录所属的分块（可顺序，可折半）
2. 在块内顺序查找

索引表中保存每个分块的最大关键字和分块的存储空间。

//索引表
typedef struct {
		int maxValue;
		int low, high;
}Index;

// 顺序表存储实际元素
int Lsit[100];
1
2
3
4
5
6
7
8

用折半查找查索引，若索引表中不包含目标关键字，则折半查找索引表最终停在$low>high$，最终要在low所指分块中查找。

查找效率分析：n个记录，均匀分为b块，每块s个记录

1. 若索引表采用顺序查找，$ASL=\frac{b+1}{2}+\frac{s+1}{2}$
2. 若索引表采用折半查找

若查找表是动态查找表，有没有更好的实现方式？链式存储

B树

//5叉排序树的结点定义
struct Node {
	int keys[4]; //最多四个关键字
	struct Node* child[5]; //最多五个孩子
	int num; //结点中几个关键字
};
1
2
3
4
5
6

如何保证查找效率？

1. 在m叉树中，规定除了根节点外，任何结点至少[m/2]个分叉，即至少含有[m/2] - 1个关键字。
2. m叉查找树中，规定对于任何一个结点，其所有子树的高度都要相同。

B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或为满足如下特性的m叉树：

（1）树中每个结点至多有m棵子树，即至多含有m-1个关键字。

（2）若根结点不是终端结点，则至少有两棵子树。

（3）除根节点外的所有非叶结点至少有[m/2]棵子树，即至少含有[m/2] - 1个关键字。

（4）所有非叶子结点的结构如下：

其中，$K_i（i=1，2，...，n）$为结点关键字，且满足$K_1<K_2<...<K_n$；$P_i(i=0,1,...,n)$为指向子树根节点的指针，且指针$P_{i-1}$所指子树中所有结点的关键字均小于$K_i$，$P_i$所指子树中所有结点的关键字均大于$K_i$， n为结点中关键字的个数。（$[m/2]-1\le n\le m-1$）

（5）所有的叶子结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指定这些结点的指针为空）。