1 线性搜索

线性搜索是一种从数组中搜索元素的算法。

即从头开始按顺序与要搜索的元素比较。

当数据量很大时，比较次数会增加，需要更多的时间。

2 二分搜索

二分搜索是一种从有序数组中搜索元素的方法。

比如：数组 [1, 2, 3, 4, 5, 6, 7, 8, 9]，查找6

  • 第一次：找到中间数5，与6比较，找到一半；
  • 第二次：找到7，与6比较，剩下6；
  • 第三次：6与6比较，相等，OK。

二分搜索利用已经排序的数组，通过将搜索数字减半而有效的搜索数字。

插值搜索

计算中间值不同：

  1. mid = low + (key-a[low])/(a[high]/a[low])*(high-low)

斐波那契查找

利用黄金分割查找，大意是从斐波那契数列中找到你要找的值位置，然后再去给定数组中查找。

3 广度优先搜索

广度优先搜索是搜索图的算法。

广度优先搜索具有从起点开始依次广泛搜索的特征。

从第一点开始，将可到达点作为候选点，然后依次到达候选点，将候选点的候选点也依次作为候选点，以此类推，直到到达搜索点为止。

4 深度优先搜索

深度优先搜索是搜索图的算法。

深度优先搜索具有深入挖掘待定路径来进行搜索的特征。

从第一点开始，将可到达点作为候选点，然后一直搜索一个候选点，直到到达搜索点为止。

5 索引

线性索引、树形索引和多级索引。

5.1 线性索引

  • 稠密索引
  • 分块索引
  • 倒排索引

稠密索引

在线性索引中，将数据集中的每个记录对应一个索引项。

6 平衡二叉树

基本思想：

在构建二叉排序树的过程中，每当插入一个节点时，先检查是否因插入而破坏了数的平衡性，若是，则找出最小不平衡子树，调整成平衡子树。

7 多路查找树

其每一个节点的孩子数可以是大于两个，且每一个节点处可以春初多个元素。

形式：

  • 2-3树
  • 2-3-4树
  • B树
  • B+树

B 树是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例。