一、定义
根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。查找按照操作方式可分为:
- 静态查找:只做查找操作
- 动态查找:在查找中同时进行插入或删除等操作
二、顺序查找
又称为线性查找,是一种最简单的查找方法。适用于线性表的顺序存储结构和链式存储结构。该算法的时间复杂度为O(n)。基本思路是从第一个元素m开始逐个与需要查找的元素x进行比较,当比较到元素值相同(即m=x)时返回元素m的下标,如果比较到最后都没有找到,则返回-1。
- 缺点:是当n很大时,平均查找长度较大,效率低;
- 优点:是对表中数据元素的存储没有要求;另外,对于线性链表,只能进行顺序查找。
三、二分查找
是一种在有序数组中查找某一特定元素的查找算法。查找过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则查找过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种查找算法每一次比较都使查找范围缩小一半,时间复杂度为 O(logn) 。
- 比较次数少,查找速度快,平均性能好
- 要求待查表为有序表,且插入删除困难。
四、插值查找
折半查找这种查找方式,不是自适应的(中间点是固定的)。二分查找中查找点计算如下:
mid=low+(high-low)/2 // 使用整数除法;避免先计算 low+high 造成溢出
通过类比,我们可以将查找的点改进为如下方式:
mid=low+(key-a[low])*(high-low)/(a[high]-a[low])
整数实现应先乘后除,避免比例提前截断为 0,并使用足够宽的整数防止乘法溢出。计算前还应检查 key 是否位于端点值之间;若 a[low] 与 a[high] 相等,则直接比较目标值,避免除以零。
基于二分查找算法,将查找点的选择改进为自适应选择,可以提高查找效率。
- 适用于关键字分布比较均匀的有序表
- 如果关键字分布非常不均匀,很可能不如二分查找
五、斐波那契查找
在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数 F[n],将原查找表扩展为长度为 F[n](如果要补充元素,则补充重复最后一个元素,直到满足 F[n] 个元素),完成后进行斐波那契分割,即 F[n] 个元素分割为前半部分 F[n-1] 个元素,后半部分 F[n-2] 个元素,找出要查找的元素在那一部分并递归,直到找到。
六、分块查找
分块查找又称索引顺序查找,它是顺序查找的一种改进方法。将n个数据元素"按块有序"划分为m块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须"按块有序";即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字;而第2块中任一元素又都必须小于第3块中的任一元素,……,基本流程:
- 先选取各块中的最大关键字构成一个索引表;
- 先对索引表进行二分查找或顺序查找,以确定待查记录在哪一块中;然后,在已确定的块中用顺序法进行查找。
七、哈希查找
哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制,那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1);如果没有时间限制,那么我们可以使用无序数组并进行顺序查找,这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。算法流程:
- 用给定的哈希函数构造哈希表
- 根据选择的冲突处理方法解决地址冲突
- 在哈希表的基础上执行哈希查找
八、树表查找
1、二叉查找树
二叉查找树对每个结点要求左子树的关键字小于该结点、右子树的关键字大于该结点(重复值需另定规则)。查找时与当前结点比较,再进入对应子树。 这个算法的查找效率很高,但是如果使用这种查找方法要首先创建树。对二叉查找树进行中序遍历,即可得到有序的数列。
- 如果经常动态查找,可以使用平衡二叉树
2、2-3查找树
和二叉树不一样,2-3树允许每个节点保存1个或者两个的值。对于普通的2节点(2-node),他保存1个key和左右两个子结点。对应3节点(3-node),保存两个Key,可以有效降低树的高度,增加查找速率。如果中序遍历2-3查找树,就可以得到排好序的序列。
3、红黑树
2-3查找树能保证在插入元素之后能保持树的平衡状态,最坏情况下即所有的子节点都是2-node,树的高度为lgn,从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂,于是就有了一种简单实现2-3树的数据结构,即红黑树,红黑树的思想就是对2-3查找树进行编码,尤其是对2-3查找树中的3-nodes节点添加额外的信息。
4、B树和B+树
B树可以看作是对2-3查找树的一种扩展,即 M 阶 B 树的每个结点最多有 M 个子结点和 M−1 个关键字。B 树是平衡的多路查找树,并不是二叉查找树。 B和B+树的区别在于,B+树的非叶子结点只包含导航信息,不包含实际的值,所有的叶子结点和相连的节点使用链表相连,便于区间查找和遍历 但是B树也有优点,其优点在于,由于B树的每一个节点都包含key和value,因此经常访问的元素可能离根节点更近,因此访问也更迅速。