查找的基本概念
查找是指在n个记录里，寻找关键字等于目标k的过程。唯一匹配数据数据元素的数据项称为主关键字，其余数据项称为次关键字。平均查找长度（ASL）反映了统计意义上的多次查找的平均查找长度。
查找表的操作
- 查找元素：判断查找表中是否存在具有特定关键字的元素。
- 检索属性：从查找表中检索出具有特定关键字的元素的属性信息。
- 插入元素：向查找表中添加一个新的元素，这通常涉及为新元素分配空间并更新查找表的结构。
- 删除元素：从查找表中移除一个具有特定关键字的元素，这通常涉及释放元素所占用的空间并更新查找表的结构。
静态查找表与动态查找表
- 静态查找表：只进行查找和检索操作，不允许插入和删除元素。这种查找表通常用于数据集合固定不变的场景。
- 动态查找表：在进行查找操作的同时，还允许插入和删除元素。这种查找表通常用于数据集合需要频繁更新的场景。
关键字
关键字是数据元素中的一个或多个数据项，用于唯一标识该元素。根据关键字的性质，可以将其分为：
- 主关键字：每个元素的主关键字值都是唯一的，可以唯一地标识一个元素。
- 次关键字：某些元素的关键字值可能相同，这种关键字称为次关键字。在次关键字下，可能存在多个具有相同关键字的元素。
查找操作
查找操作是在查找表中搜索具有特定关键字的元素的过程。根据查找的结果，可以将查找分为：
- 查找成功：在查找表中找到了具有特定关键字的元素。
- 查找不成功：在查找表中没有找到具有特定关键字的元素。
常见的查找方法
线性表查找
顺序查找（线性查找）
顺序查找是最基础的查找方法。它从线性表的第一个元素开始，逐个检查每个元素，直到找到目标值或遍历完整个线性表。
-
实现方式：
- 对于顺序表（数组），可以通过数组下标递增顺序扫描每个元素。
- 对于链表，可以通过指针
next来依次扫描每个元素。
-
算法复杂度：
- 时间复杂度：在最坏情况下，需要比较n次（n是线性表的长度），因此时间复杂度为O(n)。
- 空间复杂度：O(1)，因为不需要额外的存储空间。
-
适用场景：
- 线性表无序或元素较少的情况。
- 线性表中的数据元素频繁变动（如插入和删除操作）时，更适合使用顺序查找。
折半查找（二分查找）
折半查找要求线性表必须是有序的。它首先计算中间元素的位置，然后将目标值与中间元素的值进行比较。根据比较结果，决定在左半部分还是右半部分继续查找，直到找到目标值或搜索范围为空。
-
实现方式：
- 递归实现：通过递归函数在左半部分或右半部分继续查找。
- 迭代实现：使用循环结构在左半部分或右半部分继续查找。
-
算法复杂度：
- 时间复杂度：O(log n)，因为每次查找都将搜索范围缩小一半。
- 空间复杂度：取决于实现方式，递归实现可能需要额外的栈空间，而迭代实现则不需要。
-
适用场景：
- 线性表有序且元素较多的情况。
- 需要频繁地在线性表中查找元素时，二分查找可以显著提高查找效率。
索引查找（分块查找）
索引查找是在线性表的索引存储结构上进行的。它首先将线性表按照一定的规则分成若干个逻辑上的子表，并分别为每个子表建立一个索引项，由这些索引项构成一个索引表。查找时，首先在索引表中查找目标值所在的子表，然后在子表中顺序查找目标值。
-
实现方式：
- 分块：将线性表分成若干块，每块的结点存放是任意的，但块与块之间必须排序。
- 建立索引表：将每块的最大关键值放入索引表中作为索引值，索引表按序排列。
- 查找：首先在索引表中查找目标值所在的块，然后在块内顺序查找目标值。
-
算法复杂度：
- 时间复杂度：取决于索引表的构建和块内查找的效率。通常情况下，索引查找的时间复杂度介于O(1)和O(n)之间。
- 空间复杂度：需要额外的存储空间来存储索引表。
-
适用场景：
- 线性表较大且元素分布不均匀时，索引查找可以平衡查找效率和存储空间的需求。
- 适用于需要频繁查找且允许一定预处理时间的场景。
树表的查找
树表，即以二叉树或树作为表的组织形式。常见的树表有二叉排序树（Binary Search Tree，BST）、平衡二叉树（如AVL树和红黑树）、B树及其变种（如B+树和B*树）。这些树结构通过特定的组织方式，使得查找、插入和删除操作的时间复杂度能够保持在较低的水平。
二叉排序树（BST）
- 定义：二叉排序树或者是空树，或者是满足以下性质的二叉树：若它的左子树非空，则左子树上所有记录的值均小于根记录的值；若它的右子树非空，则右子树上所有记录的值均大于根记录的值；左、右子树本身又各是一棵二叉排序树。
- 查找：在二叉排序树上进行查找，是一个逐步缩小查找范围的过程。通过比较关键字与节点值，决定在左子树还是右子树中继续查找，直到找到目标节点或确定目标节点不存在。
- 插入：插入新节点时，需要保持二叉排序树的性质。若树为空，则新节点为根节点；否则，将新节点的关键字与根节点的关键字比较，决定插入到左子树还是右子树中。
- 删除：删除节点时，需要考虑节点的子树情况。若节点是叶子节点，则直接删除；若节点只有左子树或右子树，则用其子树代替该节点；若节点既有左子树又有右子树，则可以用其前驱或后继节点代替该节点，并删除前驱或后继节点。
平衡二叉树
- 定义：平衡二叉树是一种特殊的二叉排序树，它通过特定的机制（如旋转操作）保持树的平衡，确保树的高度不会超过O(log n)。常见的平衡二叉树包括AVL树和红黑树。
- AVL树：AVL树通过维护每个节点的平衡因子（左子树高度减去右子树高度）来实现平衡。当插入或删除节点导致平衡因子绝对值超过1时，需要进行旋转操作来调整树的平衡。
- 红黑树：红黑树通过颜色标记和旋转操作来维持近似平衡。红黑树的节点被标记为红色或黑色，并满足一系列性质，如红色节点的子节点必须是黑色、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点等。
B树及其变种
- B树：B树是一种多路平衡查找树，广泛应用于数据库和文件系统中。B树的每个节点可以有多个子节点和关键字，能够在磁盘IO操作中更高效地进行查找。
- B+树：B+树是B树的变种，具有更高的空间利用率和查询效率。B+树的所有叶子节点构成一个有序链表，使得范围查询更加高效。
- B*树：B*树是B+树的变种，进一步提高了空间利用率和查询性能。
复杂度分析
- 查找：在平衡二叉树和B树中，查找操作的时间复杂度为O(log n)，因为树的高度在平衡情况下为O(log n)，使得操作只需访问较少的节点。
- 插入：插入操作的时间复杂度也为O(log n)，因为需要找到插入位置并保持树的平衡。
- 删除：删除操作的时间复杂度同样为O(log n)，因为需要找到删除节点并调整树的平衡。
散列表查找
散列表是一种通过散列函数将关键字映射到存储位置的查找结构。它实现了关键字与存储位置之间的直接映射，从而提高了查找效率。散列表查找的核心在于散列函数的构造和冲突解决策略的选择。
散列函数的构造
散列函数是散列表查找的关键。一个好的散列函数应该具备以下特点：
- 计算简单：以便提高转换速度。
- 分布均匀：以减少冲突的发生。
常见的散列函数构造方法包括：
- 直接定址法：取关键字的某个线性函数值为散列地址，即H(key)=a×key+b，其中a和b为常数。这种方法计算简单，但要求关键字分布基本连续，否则会造成较大的空间浪费。
- 除留余数法：取关键字除以某个素数p的余数作为散列地址，即H(key)=key%p。这种方法简单常用，但要求p最好选取小于或等于表长m的最大素数。
- 数字分析法：假设有一组关键字，每个关键字由n位数字组成，从中提取数字分布比较均匀的若干位作为散列地址。这种方法适用于关键字具有某种规律的情况。
- 平方取中法：取关键字平方的中间几位作为散列地址。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀。
- 折叠法：把关键字分割成位数相同的几段（最后一段的位数可以少一些），然后将它们叠加的和（舍去最高进位）作为散列地址。这种方法适用于关键字位数较多的情况。
冲突解决策略
在散列表中，不同的关键字可能会映射到同一个存储位置，即发生冲突。解决冲突的策略主要有两种：开放定址法和拉链法。
- 开放定址法
开放定址法的基本思想是：当发生冲突时，使用某种探测方法找到一个新的空闲位置来存放该元素。常见的开放定址法包括：
* **线性探测法**：发生冲突时，每次往后探测相邻的下一个单元是否为空。这种方法容易造成同义词、非同义词的“聚集（堆积）现象”，严重影响查找效率。* **平方探测法**：以平方数为探测距离进行探测，即di=±1^2, ±2^2, ±3^2, ...。这种方法解决了线性探测法中的元素堆积问题，但会有些散列表单元永远都探测不到。* **伪随机序列法**：使用伪随机数生成探测序列，即di是一个伪随机序列。这种方法可以进一步减少冲突的发生，但实现起来相对复杂。- 2. 拉链法（链地址法）
拉链法的基本思想是：将具有相同散列地址的关键字（同义词）值放在同一个单链表中，称为同义词链表。当发生冲突时，只需将新元素插入到对应链表的末尾即可。这种方法不会造成元素堆积现象，且查找效率较高。但需要注意的是，当链表较长时，查找效率会下降。
散列表查找的过程
散列表查找的过程如下：
- 计算散列地址：根据散列函数计算目标关键字的散列地址。
- 访问存储位置：根据散列地址访问对应的存储位置。
- 处理冲突：如果存储位置已被占用且关键字不匹配，则根据冲突解决策略找到一个新的空闲位置或链表节点进行查找或插入操作。
- 返回结果：如果找到目标关键字，则返回其存储位置或对应的值；如果未找到，则返回查找失败的信息。
散列表查找的性能分析
散列表查找的性能主要取决于以下几个因素：
- 散列函数的优劣：一个好的散列函数可以减少冲突的发生，提高查找效率。
- 冲突解决策略的选择：不同的冲突解决策略对查找效率有不同的影响。拉链法通常比开放定址法具有更好的查找性能。
- 装填因子：装填因子α=n/m，其中n为填入表中的元素个数，m为散列表的空间大小。装填因子越大，冲突的可能性越大，查找效率越低。因此，在实际应用中需要合理控制装填因子的大小。
查找方法的比较
| 查找方法 | 适用场景 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 线性查找 | 无序数组 | O(n) | O(1)（不考虑存储数组的空间） |
| 二分查找 | 有序数组 | O(log n) | O(1)（不考虑存储数组的空间） |
| 分块查找 | 关键字分块存储 | 介于O(1)和O(n)之间 | O(n)（块和块内元素的存储） |
| 二叉排序树查找 | 动态插入和删除操作较多的场景 | 平均O(log n)，最坏O(n)（取决于树的结构） | O(n)（存储树的空间） |
| 哈希查找 | 需要快速查找的场景 | 平均O(1)，最坏O(n)（取决于哈希函数和冲突解决策略） | O(n)（存储哈希表的空间） |
查找算法的选择
在选择查找算法时，需要考虑数据集合的特性、查找操作的频率以及内存使用情况等因素。例如，对于静态且有序的数据集合，二分查找是一个高效的选择；对于动态插入和删除操作较多的场景，二叉排序树可能更为合适；而对于需要快速查找的场景，哈希查找通常是一个不错的选择。