查找解析

2018-10-09 本文已影响11人大大纸飞机

基本概念

仅存储数据而不获取数据是不可能的，这就是查找。查找的定义如下：

查找（Searching）就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

查找表（Search Table）是由同一类型的数据元素（或记录）构成的集合。

简单来说就是，在我们定义的数据结构中，查找位于某个位置的数据。查找又根据操作方式不同分为静态查找和动态查找两种，前者是仅获取数据不进行其他操作，后者则需要动态改变数据，比如在查找过程中插入新数据，或者删除某个已存在的数据。

接下来，对应之前介绍的几种数据结构，来说说它们各自的查找方式。

顺序表查找

顺序表，通常就是一个数组，数据在内存中按顺序排列，但并不是有序的，所以查找需要遍历，一般写法如下：

private int searchLinear1(int[] table, int data){
    // len一定要先计算出来
    int len = table.length;

    for (int i = 0; i < len; i++) {
        if(table[i] == data){
            return i;
        }    
    }
    return -1;
}

我们想当然就会写出上述代码，而且都会把数组的长度先计算出来，这算是一点小优化吧。在数据量很小的时候以上做法并没有什么问题，但是当数据量增多时，循环体每次执行i<len的判断会对时间产生非常大的影响。我们可以通过增设一个“哨兵”来去除判断，代码如下：

private int searchLinear2(int[] table, int data){
    int len = table.length;

    table[0] = data;

    int i = len-1;
    while (table[i]!=data) {
        i--;
    }

    return i;
}

这和方法1有何区别呢？可以看到，原本for循环体每次要执行三条操作，使用while时只需要两条就可以了。当数据量较大时差异会十分明显。

顺序表这种结构，天然不适合大规模数据，但它结构简单，算法简单，在很多场景下还是十分适用的。

有序表查找

顺序表的特点我们已经掌握了，很明显它的查找时间复杂度是O(n)，如果要在一亿条数据中查找，效率相对来说就太低了。如果数据是有序的，我们就可以采取一些手段大幅提升查找效率。

1. 折半查找

折半查找就和我们猜一个1-100之间的数字一样，不会有人傻傻地从1猜到100，而是先猜一个中间的数比如50，然后根据大小再猜50-100之间的数字，这样一下减少了一半，只需要几次就能猜出结果了。代码实现如下：

private int searchOrdered(int[] table, int data){
    int low, high, mid;

    low = 0;
    high = table.length-1;
    
    while(low<=high){
        mid = (low+high)/2;
        if(data<table[mid]){
            high = mid-1;
        }else if(data>table[mid]){
            low = mid+1;
        }else{
            return mid;
        }
    }

    return -1;
}

代码很好理解，折半查找的最坏时间复杂度是O(logn)。

2. 插值查找

折半查找是一种十分优秀的查找方式，但是它限定了每次都从中间取值，在一些场景下这是没有必要的，比如还是猜1-100之间的数，但是我们知道它是一个比较小的数，这时候我们还会从50开始猜吗？再举一个例子，读一本大约500页的书，第一次读了100页，下一次翻开时，我们肯定不是先翻到一半，而是翻到靠前的位置，再找到100页续读。插值查找就是针对类似这种情况的优化。

在折半查找中，我们的关键代码是mid=(low+high)/2，我们可以把它变换成如下形式：

折半查找

我们可以这样理解这个公式，low表示起始位置，(high-low)代表长度，也就是从起始位置加上长度的一半，这就是中点。所以这里的1/2相当于偏移量，如果我们改变它的值，就可以偏移到别的位置。插值查找的做法如下：

插值查找

这里的key就是目标值，分母表示的是值的范围，分子表示目标值相对最小值的差值，这样便得到了key相对于数据的偏移比例，比如最小值是50，最大值是100，目标值是60，那它所在位置相对的比例应该是1/5处，如下所示：

偏移值

原理搞清楚了，它的实现也就很清楚了，只要把折半查找里的公式换掉就可以。但是插值查找对数据要求也是很苛刻的，数据必须较为均匀地分布，只有均匀的数据才可以这样使用比例计算偏移量。因为这个偏移量最终要映射到表中，比如下面的数据：

非均匀分布

我们要从中获取10，按照插值查找的方式，第一次获取的mid值在位置0处，但实际上10却处于中点处，这就是因为表中的数据增加不均匀造成的。

3. 斐波那契查找

裴波那契查找和插值查找目的一样，都是对折半查找的优化，它主要是依据裴波那契数列的黄金分割原理。现在，我们通过一个示例演示它的原理。首先有如下数组，我们要查找的值为72：

初始值

数组下标最大值为9，在裴波那契数值8和13之间，我们把13的下标7记为k，作为分割时的初始值。然后把数组扩展到长度为13，剩余元素用最大值填充，然后建立两个指针分别指向原数组的开始和结尾，如下所示：

扩充

接下来就是确定mid指针位置，它的计算方式为：mid = low + F(k-1) - 1; 其中F(n)表示位置n的裴波那契值。所以mid的位置为7，如下所示：

mid值

现在，目标值72比mid值小，所以要把high值前移，前移方式和折半查找一样。这时查找范围从0-F(k)变为了0-F(k-1)，所以k值也要减小1，变为6，然后进行下一次比较。如下图所示：

缩小范围

现在目标值72比mid值大，所以low需要后移，这时中间的元素有多少个呢？根据裴波那契的定义F(n) = F(n-1) + F(n-2)，可以知道F(n) - F(n-1) = F(n-2) ，所以再下一次的查找相当于在F(k-2)上进行，所以k值应该减小2，变为4，如下所示：

缩小范围

此时目标值还是比mid值小，所以重复第一次操作，low与high和mid均指向了位置5，这时便完成了查找。

在上述示例中，可以发现使用裴波那契查找并没有减少查找次数，这是因为有两次查找过程在mid的左侧。裴波那契查找会把数据分成左侧长，右侧短两部分，也就是说当查找的数据在右侧时，其查询速度会比折半查找快的多，但如果是在左侧，因为每次查询的长度都比折半要长，效率反而会更差。

裴波那契查找的代码请参考文末链接。

4. 总结

在有序表上的查找主要就是以上三种方式，后两者均是在特定情况下对折半查找的优化，具体使用哪种比较合适，还要看实际的数据。

线性索引查找

线性表虽然对数据没有要求，但是查找很慢，而有序表虽然查找很快，却要求数据是有序的。很多时候，我们可能无法对数据进行排序，比如微博的回复有可能有上亿条，进行排序是不现实的。有没有办法能在数据无序情况下，又能有比较好的查找性能呢？这就要用索引。

索引，就是把一个关键字与它对应的记录相关联的过程。

可以类比查字典来简单理解索引，在字典首部的拼音表就是一种索引，每个拼音都对应着一些发音一致的汉字的位置，我们只需要查这个拼音表就可以快速定位到汉字所在的页数。也就是说不需要对汉字进行排序，只需要获取到它的拼音，把这个拼音排好序就可以提高查找效率。

索引按照结构分为线性索引，树形索引和多级索引等，这里介绍的是线性索引，树形索引一般是B树、B⁺树，会在后续介绍。

定义

线性索引，就是将索引项集合组织为线性结构，也称索引表。

线性索引按照索引方式分为很多类型，主要是以下三种：

1. 稠密索引

稠密索引就是数据集合中的每条数据都对应索引表中的一个索引项，也就是一一对应的关系。原有的数据是无序的，索引表则是有序的，这样就可以按照上方有序表方式进行查找了。稠密索引的缺点也很明显，那就是它的数据量和原数据集合一样大，这通常需要很大的内存空间。假如数据有几亿条，而计算机内存比较小，就需要多次进行IO操作，性能也会大受影响。

2. 分块索引

稠密索引解决了查找的问题，但是数据量太大，而分块索引就折中了这两个问题。就像图书馆摆放图书一样，不同种类的书会摆放在独立的架子上，但是每个架子上的书是随机摆放的，这种块间有序、块内无序的分块方式就是分块索引。显然，在块间查找时是非常快的，而在块内因为无序只能进行遍历。但是因为索引表相对较小，减少了IO操作，所以也有较好的性能。

3. 倒排索引

倒排索引是搜索技术的基础，它是根据关键字索引对应的文章等记录。搜索的处理十分复杂，这里只介绍最基本的原理。

比如有一千个网页，有可能有“朋友”、“咖啡”、“电影”等关键字，我们想筛选出所有包含“朋友”的网页，总不能每查一次，就遍历一次吧？而且每个网页中有数百上千字，这样查找效率十分低下。

遍历肯定是需要的，那我们能不能在第一次遍历之后就把需要的信息记录下来呢？这是可行的，我们只要以关键字建立索引，每个关键字记录下对应的网页地址就可以了。这样我们会得到类似下图的索引表：

倒排索引示例

这样，当我们再次搜索“朋友”时，就能够迅速找到所有的网页地址了。那么倒排查找有什么弊端呢？这就体现在它的插入和删除了，因为相同的网页地址可能被多个关键字记录，也就意味着如果要删除一个网页，就要处理所有相关记录，这给维护带来十分大的困难。当然，真正的搜索技术比这个原理复杂的多，感兴趣的朋友可以自行查阅资料进行研究。