You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.
常用查找算法

常用查找算法

. 5 min read

顺序查找

存储结构为顺序存储或链接存储的线性表

查找的时间复杂度为 $O(N)$

二分查找

元素必须是有序的

每次将目标值与中间节点的值进行比较,再判断其落入中间节点的左侧或右侧。

可以使用迭代或递归实现。

插值查找

二分查找进阶

联系查字典,将二分查找中的 $mid = \frac{low + high}{2}$ 修改为自适应的 $mid = low + (key - a[low]) / a[high] - a[low]) * (high -low)$
及将二分查找中的比例 0.5 改为自适应的值,根据关键字在表中的位置,让下一次查找更靠近关键字,从而减少了查找的次数。

插值查找一般适用于表长较大,同时关键字分布较为均匀的表。

复杂度:$O(log_2(log_2n))$

斐波那契查找

类比二分查找,当表长等于某斐波那契数时使用。

最坏情况时间复杂度为 $O(log_2n)$,期望复杂度 $O(log_2n)$

二叉树查找

二叉搜索树的特点是左子节点小于父节点,父节点小于右子节点。

此方案的查找效率较高,但是需要维护二叉树,并且在查找树严重不平衡时退化为“链表”。

将二叉搜索树进行优化,可以参考平衡二叉树、红黑树。

平衡查找树

2-3 Tree

每个节点保存1个或2个值(对应可以拥有2个或3个子节点)

性质:在一个完全平衡的2-3查找树中,根节点到每一个叶节点的距离都相同。

红黑树

红黑树的思想是对2-3查找树进行编码,特别是对其中的3-node节点添加额外的信息。

红黑树

可以想像两个红色边链接的节点对应2-3查找树中的3-node。

红黑树的定义:

  • 红色节点向左倾斜;
  • 一个节点不可能有两个红色连接;
  • 根节点到每个叶节点的黑色链接个数相同。

红黑树的应用:

  • Java: Java.util.TreeMap, Java.util.TreeSet;
  • C++: STL::map, STL::multimap, STL::multiset;
  • .NET: SortedDictionary, SortedSet

B树

B树可以看作是2-3查找树的拓展,其每个节点允许有M-1个子节点

B树的定义

  • 根节点至少有两个子节点
  • 每个节点有M-1个key,并以升序排列
  • 其他节点至少有 M/2 个子节点

基本操作演示动画:

btreebuild

B树的优点:

  • 每一个节点包含 key 和 value, 因此经常访问的元素可能距离根节点更近,可以更快访问。

B+树

B+树的定义

  • 有 k 个子节点的节点必然有 k 个关键码
  • 非叶节点仅具有索引作用
  • 叶节点存放记录相关的信息
  • 树的所有叶节点构成一个有序链表,可以按照关键码排序的次序遍历全部记录

试想一下,在文件系统中,若该文件在磁盘上的分区恰好不属于同一个父节点,此时B+树与B树的性能差异

290050048129679

如下为B+树的操作动画:

Bplustreebuild

B+树的优点:

  • 内部节点不含数据信息,内存页可以存放更多的key。
  • 数据存放紧密,具有更好的空间局部性,访问叶节点关联的数据具有更高的缓存命中率。
  • 叶节点构成有序链表,对整棵树的遍历更快。
  • 便于区间查找与搜索。(非同父节点时优势明显)

B树/B+树的应用:

  • Windows: HPFS
  • Mac: HFS, HFS+
  • Linux: ResiserFS, XFX, Ext3FS, JFS
  • 数据库: ORACLE, MySQL, SQLServer

分块查找

每一块中数据不必有序。
但快间数据有序。 (类比快排的中间步骤)

算法步骤:

  • 选取各块中的最大关键字构成索引表
  • 二分查找确定索引块
  • 索引块内顺序查找目标值

哈希查找

哈希函数:使关键字分散到指定大小的顺序结构的转换关系。

算法流程:

  • 使用哈希函数构造哈希表
  • 解决地址冲突
    • 拉链法
    • 线性探测法
  • 执行哈希查找