前言：📫 作者简介：小明java问道之路，专注于研究计算机底层，就职于金融公司后端高级工程师，擅长交易领域的高安全/可用/并发/性能的设计和架构📫 

🏆 Java 领域优质创作者、阿里云专家博主、华为云享专家🏆

🔥 如果此文还不错的话，还请👍关注、点赞、收藏三连支持👍一下博主哦

本文导读

Re：从零开始的 DS 学习 考研专业课满分大佬是怎么学习查找算法的，本文从顺序查找->二分查找>hash 查找->BST 树->优先队列->堆，帮你打开查找算法的新世纪，深入浅出，适合各个阶段的人查阅与学习，本篇篇幅较长，适合点赞+收藏。有什么错误希望大家直接指出~

一、查找的基本概念；对线性关系结构的查找,顺序查找,二分查找

查找定义：

根据给定的某个值( Key ),在查找表中确定一个其关键字等 于给定值的数据元素(或记录)

查找算法分类：

1)静态查找和动态查找注静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。2)无序查找和有序查找。无序查找：被查找数列有序无序均可；有序查找：被查找数列必须为有序数列。

平均查找长度( Average Search Length , ASL )：

需和指定 key 进行比较的关键字的个数的期望值,称为查找算法在查找成功时的平均查找长度。对于含有 n 个数据元素的查找表,查找成功的平均查找长度为: ASL = Pi*Ci 的和。Pi：查找表中第 i 个数据元素的概率。Ci ：找到第 i 个数据元素时已经比较过的次数。

顺序查找：

说明：顺序查找适合于存储结构为顺序存储或链接存储的线性表。基本思想：顺序查找也称为线形查找,属于无序查找算法。从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值 k 相比较,若相等则表示查找成功;若扫描结束仍没有找到关键字等于 k 的结点,表示查找失败。复杂度分析:查找成功时的平均查找长度为(假设每个数据元素的概率相等) ASL = 1/n(1+2+3+...+n) = (n+1)/2; 当查找不成功时,需要 n+1 次比较,时间复杂度为 O(n);所以,顺序查找的时间复杂度为 O(n)。

二分查找：

说明：元素必须是有序的,如果是无序的则要先进行排序操作。基本思想:也称为是折半查找,属于有序查找算法。用给定值 k 先与中间结点的关键字比较, 中间结点把线形表分成两个子表,若相等则查找成功;若不相等, 再根据 k 与该中间结点关键字的比较结果确定下一步查找哪个子表, 这样递归进行,直到查找到或查找结束发现表中没有这样的结点。复杂度分析:最坏情况下，关键词比较次数为 log2(n+1) ,且期望时间复杂度为 O(log2n) ;注:折半查找的前提条件是需要有序表顺序存储)对于静态查找表, 一次排序后不再变化,折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说,维护有序的排序会带来不小的工作量,那就不建议使用。

int binarySearch(int[] array, int target) {    // 查找范围起点    int start = 0;    // 查找范围终点    int end = array.length - 1;    // 查找范围中位数    int mid;    while (start <= end) {        // mid=(start+end)/2 有可能溢出        mid = start + (end - start) / 2;        if (array[mid] == target) {            return mid;        } else if (array[mid] < target) {            start = mid + 1;        } else {            end = mid - 1;        }    }    return -1;}

二、Hash 查找法，常见的 Hash 函数(直接定址法，随机数法)，hash 冲突的概念，解决冲突的方法(开散列方法/拉链法，闭散列方法/开址定址法)，二次聚集现象

Hash 查找法：

通常我们查找数据都是通过一个个地比较来进行,有一种方法,要寻找的数据与其在数据集中的位置存在一种对应的关系,通过这种关系就能找到数据的位置。这个对应关系成为散列函数(哈希函数),因此建立的表为散列表(哈希表)散列查找是关键字与在数据集中的位置一对应 通过这种对应关系能快速地找到数据,散列查找中散列函数的构造和处理冲突的方法尤为重要

常见的 Hash 函数，散列函数的构造：

构造哈希表的前提是要有哈希函数,并且这个函数尽可能地减小冲突(1)直接定址法可以取关键字的某个线性函数值为散列地址，即:f(key) = a*key + b，这样的哈希函数简单均匀不会产生冲突,但问题是这需要事先知道关键字的分布情况，适合查找表较小且连续的情况。(2)数字分析法该方法在知道关键字的情况下，取关键字的尽量不重复的几位值组成散列地址。(3)平方取中法取关键字平方后的中间几位为散列地址(4)折叠法将关键字分为位数相等的几部分最后一部分的位数可以不等然后把这几部分的值(舍去进位)相加作为散列地址。(5)除留余数法该方法为最常用的构造哈希函数方法,对于散列表长为 m 的散列函数公式为 f(key) = key mod P (p<=m) 使用除留余数法的一个经验是，若散列表表长为 m ，通常 P 为小于或等于表长的最大质数或不包含小于 20 质因子的合数。实践证明，当 p 取小于散列表长的最大质数时，函数较好。(6)随机数法选择一个随机函数,取关键字的随机函数值作为散列地址。

hash 冲突的概念：

对于不同的关键字可能得到同一哈希地址，即 key1≠key2，而(key1) = (key2)，这种现象称为冲突。

解决冲突的方法:

(1)开放定址法一旦发生冲突 ,就去寻找下一个空的散列地址,只要散列表足够大，空的散列地址总能找到，并将记录存入，公式:fi(key) = (f(key)+ di) mod m (i-12.2.3..m-1)用开放定址法解决冲突的做法是：当冲突发生时,使用某种探测技术在散列表中形成一个探测序列.沿此序列逐个单元地查找.直到找到给定的关键字,或者碰到一个开放的地址(该地址单元为空)为止(若要插入。在探查到开放的地址,则可将带插入的新节点存入该地址单元)。查找时探测到开放的地址则表明表中无待查的关键字.即查找失败。比如说,我们的关键字集合为{12,67,56,16,25,37.22,29,15,47.48,34} ,表长为 12。我们用散列函数 f(key) = key mod 12。当计算前 S 个数{12,67,56,16,25}时,都是没有冲突的散列地址,直接存入：计算 key= 37 时,发现 f(37)= 1 ,此时就与 25 所在的位置冲突。于是我们应用上面的公式 f(37) = (37)+1) mod 12=2.于是将 37 存入下标为 2 的位置。这其实就是房子被人买了于是买下一间的作法。接下来 22,29,15,47 都没有冲突,正常的存入：到了 key=48 ,我们计算得到 f(48)=0 ,与 12 所在的 0 位置冲突了,不要紧,我们 f(48) = (f(48)+ 1) mod12= 1 ,此时又与 25 所在的位置冲突。于是 f(48) = (f(48)+2) mod12=2 ,还是冲一直到 f(48) = (f(48)+6) mod 12= 6 时,才有空位,机不可失,赶快存入：我们把这种解决冲突的开放定址法称为线性探测法。

二次探测法：考虑深一步,如果发生这样的情况,当最后一个 key=34 , f(key)=10 ,与 22 所在的位置冲突,可是 22 后面没有空位置了,反而它的前面有一个空位置 ,尽管可以不断地求余数后得到结果,但效率很差。因此我们可以改进 di= 1^2, -1^2, 2^2, 2.2.... q^2, -q^2 (q <= m/2) ,这样就等于是可以双向寻找到可能的空位置。对于 34 来说,我们取 di 即可找到空位置了。另外增加平方运算的目的是为了不让关键字都聚集在某一块区域。 我们称这种方法为二次探测法。fi(key) = (f(key)+di) MOD m (di= 1^2, -1^2, 2^2, 2.2..... -q^2,q <= m/2)

(2)再哈希法再哈希法是当散列地址冲突时,用另外一个散列函数再计算- -次 这种方法减少了冲突，但增加了计算的时间。Hi = RHi(key)，i= 1, 2....k(k≤m -1)。R Hi 均是不同的哈希函数,即在同义词产生地址冲突时计算另一个哈希函数地址 ,直到冲突不再发生。这种方法不容易产生"聚集”, 但是增加了计算时间。

(3)链地址法(拉链法)链地址法解决冲突的做法是将所有关键字散列地址相同的结点链接在同-一个单链表中。若选定的散列表长度为 m ,则可将散列表定义为一个由 m 个头指针组成的指针数组 T[0..m-1]。凡是散列地址为 i 的结点,均插入到以 T[门]为头指针的单链表中。T 中各分量的初值均应为空指针。在拉链法中,装填因子α可以大于 1 ,但一般均取α ≤ 1。

如图：链地址法处理冲突时的哈希表(同一链表中关键字自小至大有序)

前面我们谈到了散列冲突处理的开放定址法，它的思路就是一旦发生了冲突，就去寻找下一个空的散列地址。那么，有冲突就非要换地方吗？我们直接就在原地处理行不行呢？可以的，于是我们就有了链地址法。将所有关键字散列地址相同的记录存储在一个单链表中，我们称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。

(4)建立公共溢出区这种方法的基本思想是：将散列表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

二次聚集现象：开放定址法会造成二次聚集的现象,对查找不利。我们可以看到一个现象 :当表中 i,i+ 1,i+2 位置上已经填有记录时,下一个哈希地址为 i，i+1，i+2 和 i+3 的记录都将填入 i+3 的位置,这种在处理冲突过程中发生的两个第一个哈希地址不同的记录争夺同一个后继哈希地址的现象称为“二次聚集”,即在处理同义词的冲突过程中又添加了非同义词的冲突。但另一方面用线性探测再散列处理冲突可以保证做到:只要哈希表未填满,总能找到一个不发生冲突的地址 Hk。而二次探测再散列只有在哈希表长 m 为形如 4j+3 (j 为整数)的素数时才可能。

三、BST 树定义,性质,ADT 及其实现,BST 树查找,插入,删除算法

BST 树（AVL 树、红黑树）定义、性质：

二叉排序树要么是空树,要么具有如下特点：1、二叉排序树中 ,如果其根节点有左子树,那么左子树上的所有节点都小于根节点的值；2、二叉排序树种 ,如果其根节点有右子树 ,那么右子树 上的所有节点都大于根节点的值；3、二叉排序树的左右子树也要求都是二叉排序树。

查找：

二叉排序树中查找某关键字时,查找过程类似于次优=叉树,在二叉排序树不为空树的前提下,首先将被查找值同树的根结点进行比较,会有 3 种不同的结果：1、如果相等,查找成功；2、如果比较结果为根结点的关键字值较大 ,则说明该关键字可能存在其左子树中；3、如果比较结果为根结点的关键字值较小 ,则说明该关键字可能存在其右子树中；

插入：

二叉排序树本身是动态查找表的一种表示形式,有时会在查找过程中插入或者删除表中元素,当因为查找失败而需要插入数据元素时,该数据元素的插入位置一定位于二叉排序树的叶子结点,并且一定是查找失败时访问的最后一个结点的左孩子或者右孩子。通过使用二叉排序树对动态查找表做查找和插入的操作,同时在中序遍历二叉排序树时,可以得到有关所有关键字的一个有序的序列。一个无序序列可以通过构建一棵二叉排序树,从而变成一个有序序列。

删除：

在查找过程中,如果在使用二叉排序树表示的动态查找表中删除某个数据元素时,需要在成功删除该结点的同时,依旧使这棵树为二叉排序树。假设要删除的为结点 p ,则对于二叉排序树来说,需要根据结点 p 所在不同的位置作不同的操作,有以下 3 种可能：1、结点 p 为叶子结点,此时只需要删除该结点,并修改其双亲结点的指针即可；2、结点 p 只有左子树或者只有右子树,此时只需要将其左子树或者右子树直接变为结点 p 双亲结点的左子树即一居民; 直接搞至父姑点之下。3、结点 p 左右子树都有。

此时有两种处理方式：

1 )令结点 p 的左子树为其双亲结点的左子树;结点 p 的右子树为其自身直接前驱结点的右子树

​

2)用结点 P 的直接前驱(或直接后继)来代替结点 p ,同时在二叉排序树中对其直接前驱(或直接后继)做删除操作。为使用直接前驱代替结点 p:

​

总结

使用二叉排序树在查找表中做查找操作的时间复杂度同建立的二-叉树本身的结构有关。即使查找表中各数据元素完全相同,但是不同的排列顺序,构建出的二叉排序树大不相同。例如:查找表{45, 24, 53,12,37 ,93}和表{12 ,24, 37 ,45, 53 , 93}各自构建的二叉排序树图下图所示：

​

使用二叉排序树实现动态查找操作的过程实际上就是从二叉排序树的根结点到查找元素结点的过程,所以时间复杂度同被查找元素所在的树的深度(层次数)有关一为了弥补二叉排序树构造时产生如图 5 右侧所示的影响算法效率的因素,需要对二叉排序树做"平衡化"处理使其成为一棵平衡二叉树。

四、平衡树(AVL)的定义,性质,ADT 及其实现,平衡树查找,插入算法,平衡因子的概念

平衡二叉树是遵循以下两个特点的二叉树：1、每棵子树中的左子 树和右子树的深度差不能超过 1；2、二叉树中每棵子树都要求是平衡二叉树其实就是在二叉树的基础上,使树中每棵子树都满足其左子树和右子树的深度差都不超过 1。

平衡因子：每个结点都有其各自的平衡因子,表示的就是其左子树深度同右子树深度的差。平衡二叉树中各结点平衡因子的取值只可能是:0、1 和-1。

五、优先队列与堆,堆的定义,堆的生成,调整算法;范围查询堆排序

优先队列：

队列是一个操作受限的线性表, 数据只能在一端进入,另一端出来,具有先进先出的性质。有时在队列中需要处理优先级的情况,即后面进入的数据需要提前出来,这里就需要优先队列。优先队列是至少能够提供插入和删除最小值这两种操作的数据结构。对应于队列的操作,插入相当于入队,删除最小相当于出队。链表,二叉查找树,都可以提供插入和删除最小这两种操作。对于链表的实现,插入需要 0(1) ,删除最小需要遍历链表,故需要 O(N)。对于二叉查找树,这两种操作都需要 O(logN) ;而且随着不停的删除最小的操作,二又查找树会变得非常不平衡;同时使用二叉树查找树有些浪费,因此很多操作根本不需要。一种较好的实现优先队列的方式是七叉堆(下面简称堆)

堆：

堆实质上是满足如下性质的完全二叉树)树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。首先堆是完全二叉树(只有最下面的两层结点度能够小于 2 ,并且最下面一层的结点都集中在该层最左边的若干位置的二二叉树),其次任意节点的左右孩子(若有)值都不小于其父亲,这是小根堆,即最小的永远在上面。相反的是大根堆,即大的在上面。

插入：

二叉堆就是一个简单的一-维 Int 数组,故不需要初始化,直接插入便可每次插入都将新数据放到数组的最后的位置。

​

删除：堆中每次都只能删除第 1 个数据。为了便于重建堆,实际的操作是将最后一个数据的值赋给根结点然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的, 如果父结点比这个最小的子结点还小说明不需要调整了,反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。