查找（顺序表查找+有序表查找+线性索引查找）_查找表

背景

搜索引擎（Google、Yander、Navar）- Search 之旅

查找概论

被查数据所在的集合，统称为查找表。

• 查找表（Search Table）是由同一类型的数据元素（或记录）构成的集合
• 关键字（Key）是数据元素中某个数据项的值，又称键值，用它可以标识一个数据元素。也可以标识一个记录的某个数据项（字段），我们称为关键码。
• 主关键字（Primary Key）是关键字可以唯一标识一个记录
• 次关键字（Secondary key）可以识别多个数据元素（或记录）的关键字。也可以理解为不以唯一标识一个数据元素（或记录）的关键字，对应的数据项就是次关键码。
  

---

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

静态查找表（Static Search Table）:只作查找操作的查找表。

• 查询某个“特定的”数据元素是否在查找表中
• 检索某个“特定的”数据元素和各种属性

动态查找表（Dynamic Search Table）：在查找过程中同时插入查找表中不存在的数据元素，后者从查找表中删除已经存在的某个数据元素。

• 查找时插入数据元素
• 查找时删除数据元素

为了提高查找效率，需要专门为查找操作设置数据结构，这种面向查找操作的数据结构称为查找结构。

逻辑上讲，查找所基于的数据结构是集合，集合中的记录之间没有本质关系。可是要想获得较高的查找性能，我们就不能不改变数据元素之间的关系，在存储时可以将查找集合组织成表、树等结构。

对于静态查表表来说：

• 应用线性表结构组织数据，可以使用顺序查找算法
• 对主关键字排序，可以应用折半查找等技术进行高效查找

动态查找，可以考虑二叉排序树的查找技术

顺序表

顺序表查找定义

散列图书可以理解为一个集合，将它们排列整齐，就如同是将此集合构成一个线性表。针对这一线性表进行查找操作，因此它就是静态查找表。

此时图书尽管排列整体，还没有分类，因此只能从头到尾或从尾到头一本一本查看。这就是顺序查找。

顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果指导最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

//顺序查找，a为数组，n为数组大小，key为要查找的关键字
int Sequential_Search(int a,int n,int key){
    int i;
    for(i=0;i<n;i++){
        if(a[i] == key){
            return i;
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10

顺序查找优化

使用哨兵优化顺序查找

int Sequential_Search2(){
    int i=0;
    if(a[n-1] == key){
        return n-1;
    }
    a[n-1] = key;
    while(a[i] != key){
        i++;
    }
    if(i == n-1){
        return -1;
    }
    return i;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

哨兵免去了查找过程中每一次比较后都要判断查找位置是否越界的技巧

总数据较多时，效率提高很大，是非常好的编程技巧

顺序查找算法：

• 最好O(1)

• 最坏O(n)

• 平均O(n)

• 缺点：n很大，查找效率很低

• 优点：算法简单，对静态查找表的记录没有任何要求

有序表

有序表查找定义

如果对图书做了有序排列，一个线性表有序时，对于查找有很大帮助。

折半查找

猜数字：100以内正整数数字

折半查找（Binary Search）技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。

折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有区域无记录，查找失败为止。

int binary_search(int[] a,int n,int key){
    int low,high,mid;
    low = 0;
    high = n-1;
    while(low <= high){
        mid = (low+high)/2;
        if(key < a[mid]){
            higt = mid-1;
        }else if(a[mid] > key){
            low = mid+1;
        }else{
            return mid;
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

根据二叉树性质，具有n个结点的完全二叉树的深度为(㏒₂n)+1性质。推导出最坏情况查找到关键字或查找失败的次数为(㏒₂n)+1

最终折半算法的时间复杂度为O(㏒n)，它显然比顺序查找的O(n)效率高很多。

插值查找

mid = (low+high)/2 = low+(high-low)/2

mid等于最低下标low加上最高下标high与low的差的一半。算法科学家将1/2进行改进。

mid = (low+high)/2;
mid = low + (high-low)*(key-a[low])/(a[high]-a[low]);//插值
1
2

插值查找（Interpolation Search）是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值公式：

插值查找的时间复杂度为O(㏒n)

• 对于表长较大，关键字分布比较均匀的查找表来说，插值的平均性能比折半要好很多
• 极端不均匀的数据，插值查找未必合适

斐波那契查找

斐波那契查找利用黄金分割原理来实现。

//n为数组最后一个元素的下标
int fibonacci_search(int[] a,int n,int key){
    //默认a数组第一个元素为0
    int low = 1;
    int high = n;
    int k = 0;
    //计算n位于斐波那契数列的位置
    while(n>=F[k]){
        k++;
    }
    //将不满的数值补全
    for(int i=0;i<F[k]-1;i++){
        a[i] = a[n];
    }
    while(low<=high){
        //计算当前分隔的下标
        mid = low+F[k-1]-1;
        if(key<a[mid]){
            high = mid-1;
            k=k-1;
        }else if(key>a[mind]){
            low=mid+1;
            k=k-2;
        }else{
            if(mid<=n){
                //如果相等mid就是查找位置
                return mid;
            }else{
                //如果mid>n说明是补全数值，返回n
                return n;
            }
        }
    }
    return -1;
}
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

斐波那契查找算法核心：

• 当key=a[mid]，查找成功
• 当key<a[mid]，新范围是第low个到第mid-1个，此时范围个数为F[k-1]-1个
• 当key>a[mid]，新范围是第mid+1个到第high个，此时范围个数为F[k-2]-1个

斐波那契查找的时间复杂度也为O(㏒n)，但就平均性能来说，斐波那契查找要优于折半查找。如果是最坏情况，比如key=1，那么始终都处于左侧长半区查找，查找效率要低于折半查找。

斐波那契查找mid的算法比顺序查找、折半查找、插值查找简单，海量的数据中会有效率的差距

三种有序表查找本质分隔点不同，各有优劣，实际开发根据数据特点综合考虑。

索引

索引定义

实际情况下，很多数据集增长非常快，比如论坛帖子和回复或者某些服务器的日志信息。如果保证这些海量数据全部按照当中的某个关键字有序，时间代价非常高昂，这种数据通常都是按先后顺序存储。

对于这样的查找表，如果快速查找需要的数据呢？办法就是-索引

索引是为了加快查找速度而设计的一种数据结构。

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

一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。

索引按照结构分：

• 线性索引
• 树形索引
• 多级索引

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

线性索引分为：

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

稠密索引

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

稠密索引要应对的可能是成千上万的数据，因此，对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列。

索引有序意味着查找关键字时，可以用到折半、插值、斐波那契等有序算法，大大提高效率。

如上图所示，如果查找关键字18，直接从右侧数据表中查找，只能顺序查找，需要6次；而如果从左侧索引表折半查询，只需要2次，可以得到18对应的指针，最终查找到结果。

缺点：稠密索引与数据集长度规模相同，对于内存有限的计算机来说，可能要反复访问磁盘，性能下降。

分块索引

图书馆藏书，最重要的特点就是分块。

稠密索引因为索引项与数据集的记录个数相同，所以空间代价很大，为了减少索引项的个数，对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项，从而减少索引项个数。

分块有序，是把数据集的记录分成了若干块，并且这些块需要满足两个条件：

• 块内无序：块内有序要付出大量的时间空间代价，通常不要求块内有序，当然有序更理想
• 块间有序：块间关键字有序，才有可能在查找时带来效率

分块有序的数据集，每块对应一个索引项，这种索引方法叫做分块索引，它的索引项结构分三个数据项：

• 最大关键码：下一块最小关键字也比这一块最大关键字大
• 存储了块中的记录个数，便于循环时使用
• 用于指向块首数据元素的指针，便于开始这一块中记录进行遍历

分块索引查找分两步：

• 分块索引表中查找关键字所在的块。利用折半、插值等算法
• 根据块首指针找到相应的块，在块中顺序查找关键码。（块中可以无序，所以只能顺序查找）

n个记录的数据集被平均分成m块，每个块中有t条记录 n = m * t，假设Lb 为查找索引表的平均查找长度，因最好与最差的等概率原则，所以lb 的平均长度为(m+1)/2，Lw 为块中查找记录的平均长度为(t+1)/2

最佳情况就是分的块数m与块中的记录数t相同，此时意味着n = m * t = t的平方，即：

分块索引的效率比顺序查找的O(n)是高了很多，不过与折半查找的O(㏒n)相比还是有不小的差距。

因此确定所在块的过程中，块间有序可以应用折半、插值等手段来提高效率

总结：分块索引兼顾了对细分块不需要有序的情况下，大大增加了整体查找的速度，所以普遍被用于数据库查找等技术的应用当中。

倒排索引

搜索引擎：什么算法技术可以达到如此高效查找呢？

如上图所示，这张单词表就是索引表，索引项的通用结构是：

• 次关键码，例如“英文单词”
• 记录号表，例如“文章编号”

其中记录号表存储具有相同关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字）。这样的索引方法就是倒排索引（inverted index）。

这种索引表中每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引。