查找算法

在本章当中，我们将会介绍一类在平常开发过程当中经常会使用的算法，那就是查找算法，关于查找算法肯定不需要多说，都是耳熟能详的，什么顺序、二分之类的就算是没有用过应该也听闻过，那么今天我们就来简单的总结整理一下查找算法的分类和一些比较常用的算法

查找算法的分类

其实简单来说，查找算法可以分为静态查找和动态查找两类

• 静态查找表示数据集合稳定，不需要添加，删除元素的查找操作
  • 对于静态查找来说，我们可以用线性表结构组织数据，这样可以使用顺序查找算法，如果我们再对关键字进行排序，则可以使用折半查找算法或斐波那契查找算法等来提高查找的效率
• 动态查找表示数据集合在查找的过程中需要同时添加或删除元素的查找操作
  • 对于动态查找来说，我们则可以考虑使用二叉排序树的查找技术，另外我们还可以使用散列表结构来解决一些查找问题

而在此基础上又可以分为无序查找和有序查找

• 无序查找，被查找数列有序无序均可
• 有序查找，被查找数列必须为有序数列

这里会涉及到一个概念，平均查找长度（Average Search Length，ASL），表示需和指定 key 进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度，对于含有 n 个数据元素的查找表，查找成功的平均查找长度为 ASL = Pi * Ci 的和

• Pi，查找表中第 i 个数据元素的概率
• Ci，找到第 i 个数据元素时已经比较过的次数

下面我们就从最简单的顺序查找开始看起

顺序查找

顺序查找又叫线性查找，是最基本的查找技术，它的查找过程是从第一个（或者最后一个）记录开始，逐个进行记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功，如果查找了所有的记录仍然找不到与给定值相等的关键字，则查找不成功

顺序查找适合于存储结构为顺序存储或链接存储的线性表

我们来稍微分析一下它的复杂度 　

• 查找成功时的平均查找长度为（假设每个数据元素的概率相等），则 ASL = 1 / n(1 + 2 + 3 + ... + n) = (n + 1) / 2
• 当查找不成功时，需要 n + 1 次比较，时间复杂度为 O(n)

所以，顺序查找的时间复杂度为 O(n)，下面来看代码如何实现

1
2
3
4
5
6
7
8
9
10

// 顺序查找，a 为要查找的数组，n 为要查找的数组的长度，key 为要查找的关键字
int Sq_Search(int *a, int n, int key) {
  int i;
  for (i = 1; i <= n; i++) {
    if (a[i] == key) {
      return i;
    }
  }
  return 0;
}

针对于上面这个实现，我们可以考虑稍微将其优化一下，所以就有了下面这样的方式

1
2
3
4
5
6
7
8
9

// 顺序查找优化方案，a 为要查找的数组，n 为要查找的数组的长度，key 为要查找的关键字
int Sq_Search(int *a, int n, int key) {
  int i = n;
  a[0] = key;
  while (a[i] != key) {
    i--;
  }
  return i;
}

如果我们设立一个比对对象，只需要依次检查数组当中的元素与我们的比对对象是否相等，下面再来看看 JavaScript 当中的实现

1
2
3
4
5
6
7
8

function Sq_Search(arr, value) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] == value) {
      return i
    }
  }
  return - 1
}

原理是类似的，都是依次对比查找，如果找到就返回该元素，否则返回 -1

二分查找

首先需要注意，二分查找是有一个前提条件的，那就是『元素必须是有序的，如果是无序的则要先进行排序操作』，二分查找也称为折半查找，首先要找到一个中间值，通过与中间值比较，大的放右边，小的放在左边，再在两边中寻找中间值，持续以上操作，直到找到所在位置为止，如果找不到返回 false，最坏情况下，关键词比较次数为 log2(n + 1)，且期望时间复杂度为 O(log2n)

折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率，但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用

下面我们来看看如何用代码进行实现，大致思路是，任意输入一个用数字 n，用折半查找法找到 n 位于数组中的位置，如果 n 不属于数组 A，则显示错误提示，下面是 C++ 的实现方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// 非递归版本
int bin_search(int a[], int value, int n) {
  int low, high, mid;
  low = 0;
  high = n - 1;
  while (low <= high) {
    mid = (low + high) / 2;
    if (a[mid] == value)
      return mid;
    if (a[mid] > value)
      high = mid - 1;
    if (a[mid] < value)
      low = mid + 1;
  }
  return -1;
}

// 递归版本
int bin_search(int a[], int value, int low, int high) {
  int mid = low + (high - low) / 2;
  if (a[mid] == value)
    return mid;
  if (a[mid] > value)
    return bin_search(a, value, low, mid - 1);
  if (a[mid] < value)
    return bin_search(a, value, mid + 1, high);
}

JavaScrip 版本如下，也有两种方式，递归和非递归，对于非递归的版本，可以使用 while

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

// 非递归版本
function bin_search(data, dest) {
  var end = data.length - 1
  var start = 0

  // 这里需要注意判断条件是 <=
  while (start <= end) {
    var m = Math.floor((end + 1) / 2)
    if (data[m] == dest) {
      return m
    }
    if (data[m] > dest) {
      end = m - 1
    } else {
      start = m + 1
    }
  }
  return false
}

// 递归版本
function bin_search(arr, val, start, end) {
  var end = end || arr.length - 1
  var start = start || 0

  // 这里是条件
  var mid = Math.floor((start + end) / 2)

  if (arr[mid] == val) {
    return mid
  } else if (arr[mid] > val) {
    return bin_search(arr, val, start, mid - 1)
  } else {
    return bin_search(arr, val, mid + 1, end)
  }
}

插值查找

插值查找简单来说就是针对于二分查找的改进，在介绍插值查找之前，首先考虑一个新问题，为什么上述算法一定要是折半，而不是折四分之一或者折更多呢？打个比方，在英文字典里面查 apple，你下意识翻开字典是翻前面的书页还是后面的书页呢？如果再让你查 zoo，很显然这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻，同样的，比如要在取值范围 1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找 5，我们自然会考虑从数组下标较小的开始查找

经过以上分析，折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的），二分查找中查找点计算如下 mid = (start + end) / 2，即 mid = start + 1 / 2 * (end - start)，通过类比，我们可以将查找的点改进为 mid = start + (key - a[start]) / (a[end] - a[start]) * (end - start)，也就是将上述的比例参数 1 / 2 改进为自适应的，根据关键字在整个有序表中所处的位置，让 mid 值的变化更靠近关键字 key，这样也就间接地减少了比较次数

简单来说，就是将查找点的选择改进为自适应选择，可以提高查找效率，当然它也属于有序查找，有以下两点需要注意的

• 一般对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多
• 反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择

插值查找如果查找成功或者失败的时间复杂度均为 O(log2(log2n))，与二分查找可以分情况来进行使用，下面来看看代码的实现方式，下面是 C++ 的实现方式

1
2
3
4
5
6
7
8
9

int bin_search(int a[], int value, int low, int high) {
  int mid = low + (value - a[low]) / (a[high] - a[low]) * (high - low);
  if (a[mid] == value)
    return mid;
  if (a[mid] > value)
    return bin_search(a, value, low, mid - 1);
  if (a[mid] < value)
    return bin_search(a, value, mid + 1, high);
}

下面再来看看 JavaScript 当中的实现，其实原理都是一样的，都是针对基准点的调整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

function bin_search(arr, val, start, end) {
  var end = end || arr.length - 1
  var start = start || 0

  // 这里是改进的地方
  var mid = start + (val - arr[start]) / (arr[end] - arr[start]) * (end - start)
  
  if (arr[mid] == val) {
    return mid
  } else if (arr[mid] > val) {
    return bin_search(arr, val, start, mid - 1)
  } else {
    return bin_search(arr, val, mid + 1, end)
  }
}

斐波那契查找

在介绍斐波那契查找算法之前，我们先介绍一下很它紧密相连并且大家都熟知的一个概念，黄金分割

黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为 1 : 0.618 或 1.618 : 1，0.618 被公认为最具有审美意义的比例数字，这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用，因此被称为黄金分割，我们可以发现，在斐波那契数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ... 当中，随着斐波那契数列的递增，前后两个数的比值会越来越接近 0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中

下面我们来看看斐波那契查找的基本思想，它其实也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率，同样地，斐波那契查找也属于一种有序查找算法，该方法的主要思路为

先在斐波那契数列 F 中找到第 k 项，使其满足 F[k] - 1 > 有序数组的最大索引号 > F[k - 1] - 1，然后将数组扩充到长度为 F[K] - 1，并使扩充项的值都等于有序数组的最后一项，分割点的索引为 mid = low + F[K - 1] - 1，此时有序数组被 mid 划分为两段，左段长度为 F[K - 1] - 1，右段长度为 F[k - 2] - 1，若查找值大于 mid 值，则 low 等于 mid + 1，而 k = k - 2，若查找值小于 mid，则 high = mid - 1, k = k - 1

也就是如下图所示

最坏情况下，时间复杂度为 O(log2n)，且其期望复杂度也为 O(log2n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

function search(array, value) {
  let low = 0, high = array.length - 1, n = array.length - 1
  let mid, k = 0

  // 构建一个长度大于 array 数组的斐波那契数组
  var F = []
  F[0] = 0
  F[1] = 1
  for (var i = 2; i < high + 5; i++) {
    F[i] = F[i - 1] + F[i - 2]
  }

  // 寻找第 k 项
  while (high > F[k] - 1) {
    k++
  }

  // 补全有序数组
  for (let i = high; i < F[k] - 1; i++) {
    array[i] = array[high]
  }

  while (low <= high) {
    mid = low + F[k - 1] - 1
    if (array[mid] > value) {
      high = mid - 1
      // 长度缩减为 F[k - 1] - 1
      k = k - 1
    } else if (array[mid] < value) {
      low = mid + 1
      // 长度缩减为 F[k - 2] - 1
      k = k - 2
    } else {
      // 相等则找到位置
      if (mid <= n)
        return mid
      else
        // 大于原始长度，则说明等于数组最后一项
        return n
    }
  }
  return -1
}

线性索引查找

前面介绍的几种查找的算法都是基于数据『有序』的基础上进行的，但是在实际的应用中，很多数据集可能有惊人的数据量，面对这些海量的数据，要保证记录全部按照当中的某个关键字有序，其时间代价是非常昂贵的，所以这种数据通常都是按先后顺序存储的，那么如何能够快速的查找到需要的数据呢？办法就是『索引』

索引就是把一个关键字与它对应的记录相关联的过程，一个索引有若干个索引项构成，每个索引项至少应包括『关键字』和『对应的记录在存储器中的位置』等信息，在索引表中的每个索引项对应多条记录，则称为『稀疏索引』，若每个索引项唯一对应一条记录，则称为『稠密索引』，索引按照结构可以分为『线性索引』、『树形索引』和『多级索引』，所谓的线性索引就是将索引项集合组织为线性结构，也称为索引表

稠密索引

稠密索引是指在线性索引表中，将数据集中的每个记录对应一个索引项，并且索引项一定是按照关键码有序的排列，索引项有序也就意味着，在查找关键字时，可以用到折半、插值、斐波那契等有序的查找算法，如下图所示

稠密索引的改进的地方在于它简化了庞大的原数据集，使原本不能装入内存的庞大的数据集，能一次性的装入内存，并且能够在内存中实现关键字码的排序，并且每一个索引项能够指向磁盘中它代表的原数据记录，能利用高级的查找算法，这显然是稠密索引的优点，但是如果数据集非常的大，那么索引表也是非常的大，对于内存有限的计算机来说，不得不把索引表也放到磁盘中，这样就大大的降低了效率

分块索引

稠密索引因为索引项与数据集的记录个数相同，所以空间代价很大，为了减少索引项的个数，我们可以对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项（类似于图书馆的分块），分块有序是把数据集的记录分成了若干块，并且这些块需要满足两个条件

• 块内无序，每一块内的记录不要求有序
• 块间有序，比如要求第二块所以记录的关键字均要大于第一块中所有记录的关键字，第三块要大于第二块，因为只有块间有序才有可能在查找时带来效率

对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做『分块索引』

上图中定义的索引项的结构分为三个数据项

• 最大关键码，它存储了每一块中的最大关键字，这样的好处是可以使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大，当然这个索引关键字码可以是任何能够唯一标识一个块的任何数据
• 存储了块中记录的个数，以便于循环时使用
• 用于指向块首数据元素的指针，便于开始对这一块中记录遍历

在分块索引表中查找，可以分为两步

• 在分块索引表中查找要查的关键字所在块，由于分块索引表是块间有序的，因此很容易利用折半插值等算法得到结果
• 根据块首指针找到相应的块，并在块中顺序查找关键码，因为块中可以是无序的，因此只能顺序查找

假设有 m 块，每块中共有 t 条记录，显然 n = m * t，故而 ASL = (m + 1) / 2 + (t + 1) / 2 = (n / t + t) / 2 + 1，上式的最小值即 n / t = t， n = t ^ 2，则最小的 ASL = n ^ (1 / 2) + 1，分块索引的效率比顺序查找 O(n) 高了很多，总的来说分块索引在兼顾了对细分块不需要有序的情况下，大大增加了整体查找的速度，所以普遍被用于数据库查找等技术的应用当中

倒排索引

倒排索引（Inverted Index），是一种索引方法，常被用于全文检索系统中的一种单词文档映射结构，现代搜索引擎绝大多数的索引都是基于倒排索引来进行构建的，这源于在实际应用当中，用户在使用搜索引擎查找信息时往往只输入信息中的某个属性关键字，如一些用户不记得歌名，会输入歌词来查找歌名，输入某个节目内容片段来查找该节目等等

面对海量的信息数据，为满足用户需求，顺应信息时代快速获取信息的趋势，聪明的开发者们在进行搜索引擎开发时对这些信息数据进行逆向运算，研发了『关键词 —— 文档』形式的一种映射结构，实现了通过物品属性信息对物品进行映射时，可以帮助用户快速定位到目标信息，从而极大降低了信息获取难度，倒排索引又叫反向索引，它是一种逆向思维运算，是现代信息检索领域里面最有效的一种索引结构

索引项的结构是次关键字码和记录号表，其中记录号表存储具有相同关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字），这样的索引方法就是倒排索引，如下图所示

倒排索引源于实际应用中需要根据属性（或字段、次关键码）的值来查找记录，这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址，由于不是由记录来确定属性值，而是由属性来确定记录的位置，因而称为『倒排索引』

倒排索引的优点显然是查找记录非常快，基本等于生成索引表后，查找时都不用去读取记录，即可以得到结果。但是它的缺点是这个记录号不定长，可多可少