常用查找算法总结
图片来自极客时间专栏《数据结构与算法之美》
# 二分查找
# 思路
二分查找针对的是一个有序的数据集合，每次和区间的中间元素对比，把待查找的区间缩小一半，直到找到元素或区间长度为0。
# 特点
- 效率非常高，时间复杂度O(logn)
# 局限性
二分查找依赖顺序表结构（数组），其他数据结构均不支持
针对有序数据
数据量太小，二分查找和顺序查找没有太大区别
数据量太大，要求内存空间连续存储很大的数据数据，比较吃力。
# 跳表
对链表稍加改造，就可以支持类似二分查找的算法，改造之后的数据结构就是跳表。
Redis中的有序集合就是用跳表实现的。
# 思路
对于单链表来说，即使链表中存储的数据是有序的，查找数据依然只能从头往后遍历。通过建立一级甚至多级索引，可以加快查找速度：
多级索引可以带来非常大的查找效率提升，如图：
# 特点
效率非常高，达到O(logn)
由于要建立多级索引，需要消耗更多存储空间，空间复杂度O(n)
# 散列表
# 原理
散列表把键通过散列函数（哈希函数）计算得到散列值，每次访问一个元素的之后只需要进行该计算就可以定位到元素存储的位置。
散列函数非常重要，也有很多算法，散列函数在设计时，有三点基本要求：
散列函数计算得到的散列值是一个非负整数
如果 key1 = key2，那 hash(key1) == hash(key2)
如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)
不过，第三点在真实情况下几乎不可能实现，会存在键虽然不同，但是散列值相同的情况，称为散列冲突。要解决散列冲突，常用的方法有两类：开放寻址法、链表法
# 开放寻址法
开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。而重新探测新位置的方法，有线性探测法、二次探测法、双重散列：
线性探测法当发现散列值已经被占用后，就从当前位置开始依次向后查找，直到找到第一个空闲位置。
二次探测法在线性探测法的基础上进行改进，每次向后查找时的步长是线性探测法的二次方，即0、1^2、2^2...
双重散列法使用一组散列函数，如果前面的散列函数计算的位置被占用，就用后面的函数直到找到空闲位置为止。
# 链表法
更加常用，每个散列表中的“桶”或“槽“都会对应一条链表，散列值相同的元素就加入到链表中。
# 二叉查找树
# 思路
二叉查找树要求在树中的任意一个节点，左子树中每个节点的值都小于这个节点的值，右子树中每个节点的值都大于这个节点的值
在查找时，因为直到左右子树的值和其父节点的大小关系，利用该关系递归查找即可。
# 特点
中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度O(n)
二叉查找树最理想的情况，是一颗完全二叉树时，时间复杂度是O(log2n)；但如果二叉查找树退化成了一根棍子，时间复杂度是O(n)
# 平衡二叉查找树
# 思路
平衡二叉查找树的严格定义是：二叉树中任意一个节点的左右子树的高度相差不能大于1。
实际上，很多平衡二叉树没有严格符合定义，AVL树是严格符合该定义的。
平衡二叉树的作用，就是让树的高度相对更低一些，不会出现时间复杂度退化成O(n)的情况。
# 红黑树
# 思路
红黑树就是一种平衡二叉树。红黑树满足如下定义：
根节点是黑色的
每个叶子节点都是黑色的空节点，也就是说，叶子节点不存储数据
任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的
每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点
其中，第二点主要是为了简化代码实现设置的。后图中将不考虑该定义。如下是红黑树的实例：
# 特点
- 插入、删除、查找操作的时间复杂度都是O(logn)，性能非常稳定