算法：查找

查找是非数值数据处理中一种基本运算，查找运算的效率与查找表所采用的数据结构和查找方法密切相关。查找表是指由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着完全松散的关系，可以将查找表构造为静态的或者动态的。
根据对表中数据的处理有：

1. 静态查找表：不进行修改表结构的操作。如查询某个特定的数据元素是否在查找表中；检索某个特定的数据元素的属性。
2. 动态查找表：是动态变化的，除了查询和检索，对查找表要进行的操作有：插入一个数据元素和删除一个数据元素。

表中数据的查找通过关键码进行区分。关键码是数据元素(或记录)的某个数据项的值，用它来识别(标识)这个数据元素(或记录)。主关键码是指能唯一标识一个数据元素的关键码。次关键码是指能标识多个数据元素的关键码。
查找算法的基本操作：将记录的关键码与给定值进行比较。
对于含有n个记录的表，查找成功时的平均查找长度定义为：
$$ASL=\sum _{i=1}^n{P}_i{C}_i$$
$P_i$为表中第i个记录进行查找的概率，且${\sum }_{i=1}^n{P}_i=1$；$C_i$为找到表中其关键码与给定值相等的记录时和给定值已进行过比较的关键码个数。

1. 顺序查找和折半查找

当仅在查找表中进行查找运算而不修改查找表时，可先构造一个静态查找表，然后进行顺序查找或折半查找等操作。

1.1 顺序查找

顺序查找的方法对于顺序查找和链式查找存储方式的线性表都适用。
在等概率情况下，顺序查找成功的平均查找长度是：
$$AS{L}_{ss}=\sum _{i=1}^n{P}_i{C}_i=\frac{1}{n}\sum _{i=1}^n(n-i+1)=\frac{n+1}{2}$$

成功查找的平均比较次数约为表长的一半。若所查记录不在表中，则至少进行n次比较才能确定查找失败。与

• 缺点：顺序査找方法在"值较大时，其平均查找长度较大，查找效率较低。
• 优点：算法简单且适应面广，对查找表的存储结构没有要求，无论记录是否按关键码有序排列均可应用。

1.2 折半查找

折半查找也称为二分查找，该方法是将给定值与中间位置记录的关键码比较，若相等，则查找成功:若不等，则缩小范围，直至新的査找区间中间位置记录的关键码等于给定值或者查找区间没有元素时(表明查找不成功)为止。

• 使用范围：表中的元素已经按关键码排序。

1. 整型数组折半查找

int Bsearsh_1(int r[], int low, int high, int key)
/*元素存储在r[low, high],用折半查找的方法在数组r中找值为key的元素*/
/*若找出则返回元素的下标，否则返回-1*/
{
	int mid;
	while(low<=high){
		mid=(low+high)/2;
		if(key==r[mid]) return mid;
		else if(key<r[mid]) high = mid-1;
			else low=high+1;
	}
	return -1;
}

2. 整型数组折半查找递归算法

int Bsearsh_rec(int r[], int low, int high, int key)
{
	int mid;
	if(low<high){
		mid=(low+high)/2;
		if(key==r[mid]) return mid;
		else if(key<r[mid]) return  Bsearsh_rec(r, low, mid-1, key);
			else return  Bsearsh_rec(r, mid+1, high, key);
	}
	return -1;
}

折半查找可以理解为折半查找树。以当前查找区间的中间位置上的记录为根，左子表和右子表中的记录分贝作为根的左子树和右子树结点。

具有n个结点的判定树的高度为$[lo{g}_{2}n]+1$,所以折半查找在查找成功时和给定值进行比较的关键码个数至多为$[lo{g}_{2}n]+1$。
折半查找的平均查找长度为：
$$AS{L}_{bs}=\sum _{j=1}^n{P}_i{C}_i=\frac{1}{n}\sum _{j=1}^{n}j\times 2^{j-1}=\frac{n+1}{n}lo{g}_2(n+1)-1$$
当n值较大时，
$$AS{L}_{bs}\approx lo{g}_2(n+1)-1$$

• 折半查找的效率很高，但是查找表需要采用顺序存储并且关键码要有序排列。折半查找适用于查找不易变动，且又经常进行查找的情况。

1.3 索引顺序查找

在分块查找过程中，首先将查找表分成若干块，每一块中关键码不一定有序，但块之间是有序的，即后一块中所有记录的关键码均大于前一个块中最大的关键码。此外，还建立了一个’索引表”，索引表的元素按关键码有序排列。因此，查找过程分为两步:第-步在索引表中确定待查记录所在的块;第二步在块内顺序查找。
平均查找长度为：
$$AS{L}_{bs}=\frac{1}{2}(\frac{n}{s}+s)+1$$
其中，b为分的块数；s为每块内的元素数量。当s取$\sqrt{n}$时，$AS{L}_{bs}$取最小值$\sqrt{n}+1$

2. 树表查找

将查找表组织为一种树状结构时，则为树表查找。
非空的二叉查找树中左子树上所有结点的关键码均小于根结点的关键码，右子树上所有结点的关键码均大于根结点的关键码，因此，可将二叉查找树看成是一个有序表，其查找过程与折半查找过程相似。
二叉树数据结构及存储

typedef struct Tnode{
	int key;
	struct Tnode *lchild,*rchild;
}BSTnode,*Bitree;

2.1 查找

Bitree searchBST(Bitree root, int thekey, Bitree *father)
/*在root指向根的二叉查找树中查找键值为key的结点*/
/*若找到则返回所指向的节点指针，否则返回NULL，并向father带回父节点的指针*/
{	Bitree p=root; *father = NULL;
	While(p&&p->key!=thekey){
	*father = p;
	if(thekey<p->key) p=p->lchild;
	else p=p->rchild;
	}
	return p;
}

2.2 插入

构造二叉树：关键码序列 { 46 , 25 , 54 , 13 , 29 , 91 } \{46,25,54,13,29,91\} {46,25,54,13,29,91},则其构造的过程为：

代码实现：
二叉查找树的插入是不断向下延展的，不会在中间结点位置插入。
此代码是在查找的基础之上进行的实现。

Bitree insertBST(Bitree *root, int newkey)
/*在*root指向根的二叉查找树中插入一个键值为newkey的结点，若插入成功则返回0，否则返回-1*/
{	Bitree s,p,father;
	s = (BSTnode *)malloc(sizeof(BSTnode));
	if(!s) return -1;
	s->key = newkey;s->lchild =NULL;s->rchild = NULL;
	P = searchBST(*root,newkey,&father);  //查找插入位置
	if(p) return -1;                      //键值为newkey的结点已在树中，不再插入
	if(!father) *root=s;                  //若为空树，键值为newkey的结点为树根
	else if(newkey <father->key) father->lchild = s;
		else  father->rchild = s;
	return 0;
}

另外，由于一棵二叉查找树的形态完全由输入序列决定，所以在输入序列已经有序的情况下，所构造的二又查找树是一棵单枝树。从二又查找树的查找过程可知，这种情况下的査找效率和顺序查找的效率相当。

3. 哈希表及哈希查找

与散列表结合使用。

顺序查找、折半查找和二叉查找表的存储位置和关键码之间不存在确定的关系，查找过程要通过系列对关键码的比较后才能确定记录在表中的位置。
理想情况是依据记录的关键码直接得到其对应的存储位置，即要求记录的关键码与其存储位置之间存在一一对应关系，从而快速地找到记录。

3.1 哈希造表

根据设定的哈希函数 Hash(key)和处理冲突的方法，将一组关键码映射到一个有限的连续的地址集(区间)上，并以关键码在地址集中的“像”作为记录在表中的存储位置，这种表称为哈希表，这一映射过程称为哈希造表或散列，所得的存储位置称为哈希地址或散列地址。

利用哈希函数来对应关键码和存储位置，必须做到一一对应，每次映射的结果是统一的。
采用哈希法需要解决两个问题：

1. 哈希函数的构造；
2. 冲突的解决。

• 冲突
  对于某个哈希函数 Hash 和两个关键码$K_1$和 $K_2$，如果 $K_1\ne K_2$,而 $Hash(K_1)=Hash(K_2)$，则称出现了冲突，对该哈希函数来说，$K_1$和 $K_2$称为同义词。

3.2 处理冲突

处理冲突就是为出现冲突的关键码找到另一个空的哈希地址。
常见的处理冲突的方法有开放定址法、链地址法(拉链法)、再哈希法、建立公共溢出区法等，在处理冲突的过程中，可能得到一个地址序列，记为$H_i(i=1,2,...,k)$。

开放定址法

$$\begin{array}{cc}{H}_i=(Hash(key)+d_i)\%m& i=1,2,...,k(k\le m-1)\end{array}$$
其中，Hash(key)为哈希函数；m为哈希表的表长；$d_i$为增量序列。常见增量序列有：

1. $d_i=1,2,...,m-1$,称为线性探测再散列。
2. $d_i=1^2,-1^2,2^2,-2^2,3^2,...,-k^2(k\le \frac{m}{2})$,称为二次探测再散列。
3. $d_i=伪随机序列$，称为随机探测再散列。

最简单的就是进行线性探测，发生冲突时顺序的存储到下一个单元进行探测，直到找到空闲的地址。


线性探测法可能使第i个哈希地址的同义词存入第 +1 个哈希地址，这样本应存入第 i+1个哈希地址的元素变成了第 i+2 个哈希地址的同义词，……，因此，可能出现很多元素在相邻的哈希地址上“聚集”起来的现象，大大降低了查找效率。为此，可采用二次探测法或随机探测再散列法，以降低“聚集”现象。

链地址法

链地址法是一种经常使用且很有效的方法。它将具有相同哈希函数值的记录组织成一个链表，当链域的值为 NUIL 时，表示已没有后继记录。
例如，哈希表表长为 11、哈希函数为 $Hash(key)=key\mathrm{mod}11$，对于关键码序列 47，34，13,12，52，38，33，27，3，使用链地址法构造的哈希表。

3.3 哈希查找

在线性探测法解决冲突的哈希表中进行查找的过程如下：

1. 先根据哈希函数计算出元素的哈希地址。
2. 若是空单元，说明查找不成功，可结束查找:若不是空单元，则与该单元中的元素进行比较。
3. 若相等，则查找成功并结束查找，否则，计算出下一个哈希地址，转(2)。

在用链地址法解决冲突构造的哈希表中查找元素，就是根据哈希函数得到元素所在链表的头指针，然后在链表中进行顺序查找即可。