关于查找、搜索算法

一、顺序查找，遍历元素查找，线性查找

• 元素无序排列
• 顺序存储和链式存储都可以
• 用于数组、vector、deque、list链表
• 时间复杂度，最好是O(1)即在遍历开始就查找到,最差是O(n)即在遍历最后才找到。平均查找次数n/2，所以平均复杂度O(n)。
• 优化技巧，将要查找的key设置成头元素或尾元素，当做哨兵。然后用while循环比较当前元素和哨兵是否相等，可以减去元素下标是否到达边界的比较。

大话数据结构

• 优缺点及适用场合

二、有序且顺序存储的快速查找

• 元素有序排列
• 顺序存储的数组、vector、deque，因为涉及到指针直接跳n步，所以不适合链式存储的

2.1、二分查找、折半查找

• 算法实例，重点就是将key与mid中间值比较，然后更新low和high值为mid值

• 时间复杂度和适用场景

2.2、插值查找

• 想象我们实际生活中翻字典查找英文单词，如果要查"apple"，肯定会首先翻字典最前面的部分查找；同样在查"zoo"时，会直接翻到最后面的部分查找。而不是像折半查找那样，先翻到中间，然后再折半折半。
• 这种均匀分布的数据，就可以更精确地跳到合适的地方去查找，优于折半

2.3、斐波那契查找、黄金分割查找

• 先用数组保存一个全局的菲波那切数列{0,1,1,2,3,5,8,13,21,34...}，用于后面取用。
• 斐波那契数列有叫黄金分割数列，是指当F[k] = F[k-1]+F[k-2]，并且k趋近于无穷时F[k-1]/F[k]非常接近于0.618这个黄金比例。如2/3=0.666,3/5=0.6,5/8=0.625,8/13=0.615,13/21=0.619。。。

》【总结】
1、数据分布比较均匀，用插值查找
2、数据分布不均匀且大量时，用斐波那契（黄金分割）查找会比二分查找效率高一点
3、图省事就用二分查找，写代码简单

三、线性索引查找

• 索引是为了加快查找速度而特别设计的一种数据结构。
• 这种索引表记录了一个关键字和对应的数据节点的地址。通过查询这个额外的数据线性索引表，就可以找到数据实际的地址在哪，而不用直接去遍历真实数据查询。

3.1、稠密索引

• 稠密索引是指在线性索引中，将每个真实数据都对应一个索引项，然后将索引项组成一个大的索引表。
• 换句话说，就是给无序的数据项另外建立一个有序的关键字索引表。且索引项与数据项的个数相同。

• 稠密索引的优缺点

3.2、分块索引

• 图书馆的书籍并不是按顺序摆放，而是分类分房间存放，然后每一类里面再分书架摆放，书架里在分块摆放接近序号的书籍。这样找书的时候，我们先按照网上查到的序列号找到对应的房间，再找到对应的书架，再找到大致的区域，然后仔细遍历查找书的位置（因为最后可能部分书的摆放不是完全有序的）。
• 分块，块间有序，快内无序（也可以多花时间排序）

• 索引项数据结构

• 分块索引的复杂度分析

3.3、倒排索引——最基础的网页搜索技术

• 倒排索引实例

• 倒排索引的由来：不是先找到数据项再去找里面的某个属性值，而是根据某个属性值反过来（倒过来）寻找到整个数据项，然后再获取其他想要的属性。

四、二叉排序树（Binary Sort Tree——BST）二叉搜索树

• 动态查找表：需要在查找时插入和删除数据的查找表。排序的顺序存储表虽然查找快速，但是在插入和删除数据时，将会移动大量数据，效率较低。（如果是无序的表，那在删除的时候还可以将最后一个元素补到删除的位置，这样也可以提高效率。）
• 链式存储的数据表，在插入和删除数据时，只是改动几根指针的指向，效率很高。因此，当我们需要做动态查找表时，因尽量用链式结构来存储数据。
• 二叉树就是一种链式存储的结构。

• 【二叉排序树】是指将一颗二叉树进行中序遍历输出，能得到一个从小到大排列的序列。因此二叉排序树的性质就是左子树都比小于它的根节点，右子树都大于它的根节点。而且它的左右子树也都是二叉排序树。

  
  

4.1、二叉排序树的构建

借用二叉树的插入操作来进行构建。在C++中可直接使用set集合，底层也是个二叉排序树（红黑树）

4.2、二叉排序树的插入

要先用二叉排序树的查找操作，判断当前树是否已经存在这个关键字，若是已经存在就不插入了。若是不存在，则根据查找返回的节点当做父节点，再根据小左，大右原则插入。

4.3、二叉排序树的查找

4.4、二叉排序树删除节点

删除节点比较重要，先是要用到查找，找到后在删除（free释放内存）该节点之前还要安排好周围节点的关系，即需要重新调整二叉树，使得满足（左小右大）中序遍历后是排序。即要保证删除该节点后，剩下的节点还能是一个二叉排序树。

image.png