数据结构(20)-查找初探

概念

查找技术和我们日常的生活息息相关，比如上网搜索信息、在手机通讯录里查找某一个联系人。所有这些需要被查找的数据所在的集合，统称为查找表。

查找(Searching): 就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素。

关键字Key是数据元素中某个数据项的值，又称为键值。若此关键字可以唯一的标识一个记录，则称之为主关键字(Primary Key)，对于可以识别多个数据元素(或者记录)的关键字，我们称之为次关键字(Secondary Key)。

查找表

查找表(Search Table)是由同一类型的数据元素(或者记录)构成的集合。
按照查找表操作方式，查找表可以分为两类：静态查找表、动态查找表。

静态查找表(Static Search Table): 只作查找操作的查找表。主要操作如下：

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

动态查找表(Dynamic Search Table): 在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。操作如下：

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

对于静态查找表来说，我们可以使用线性表结构来组织数据，这样使用顺序查找法、折半查找等方式都比较高效；对于动态查找表，可以考虑二叉排序树查找。

顺序表查找

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

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

也可以使用添加“哨兵”的方式进行优化，数组的第一个元素空置：

int Sequential_Search2(int *a, int n, int key) {
    int i;
    //设置a[0]为关键字值,称为'哨兵'
    a[0] = key;
    //循环从数组尾部开始
    i = n;
    while (a[i] != key) {
        i--;
    }
    //返回0,则说明查找失败
    return i;
}

由代码可以看出，顺序表查找的时间复杂度为 $O(n)$ ，一般适用于小型数据查找。

有序表查找

折半查找

有序表的查找可以使用折半查找，也就是二分查找，它的前提是线性表中的记录必须是关键码有序，线性表必须采用顺序存储。折半查找的基本思想是：在有序表中，取中间记录作为⽐较对象，若给定值与中间记录的关键字相等则查找成功；若给定值⼩于中间的记录关键字，则在中间记录的左半区继续查找；若给定的值⼤于中间记录的关键字，则在中间记录的右半区继续查找；不断重复以上的过程，直到查找成功，或所以查找区域无记录，查找失败为⽌。代码实现如下：

//假设数组a,已经是有序的(从小到大)
int Binary_Search(int *a, int n, int key) {
    int low, high, mid;
    low = 1;
    high = n;
    
    while (low <= high) {
        mid = (low + high) /2;
        if (key < a[mid]) {
            //若key比a[mid] 小,则将最高下标调整到中位下标小一位;
            high = mid - 1;
        } else if (key > a[mid]) {
             //若key比a[mid] 大,则将最低下标调整到中位下标大一位;
            low = mid + 1;
        } else {
            //若相等则说明mid即为查找到的位置;
            return mid;
        }
    }
    
    return 0;
}

由代码可以看出，二分算法的时间复杂度为 $O(logn)$ 。

插值查找

插值查找是根据要查找的关键字 $key$ 与查找表中最大最小记录的关键字比较后的查找方法，是对折半查找进行优化。其核心公式如下：

$mid = low + \frac{key - a[low]}{a[high] - a[low]} \left( high - low\right)$

其时间复杂度也为 $O(logn)$ 。但是对于关键字分布比较均匀的查找表来说，插值查找算法的平均性能要比折半查找好得多。

斐波那契查找

使用斐波那契查找，首先要生成一个斐波那契数列的数组。

F[0]=0;
F[1]=1;
for(i = 2; i < T_MAX_SIZE; i++) {
    F[i] = F[i-1] + F[i-2];
}

斐波那契查找的核心如下：

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

查找代码如下：

int F[T_MAX_SIZE];

int fibonacciSearch(int *a, int n, int key) {
    int k = 0;
    while (n > F[k] - 1) {
        k++;
    }
    
    for (int i = n; i < F[k] - 1; i++) {
        a[i] = a[n];
    }
    
    int low = 1;
    int high = n;
    int mid;
    while (low <= high) {
        mid = low + F[k-1] - 1;
        if (key < a[mid]) {
            high = mid - 1;
            k = k - 1;
        } else if (key > a[mid]) {
            low = mid + 1;
            k = k - 2;
        } else {
            return mid <= n ? mid: n;
        }
    }
    
    return 0;
}

由代码可知，斐波那契查找的时间复杂度为 $O(logn)$ ，但是平均性能来说，斐波那契查找要优于折半查找。

三种有序表查找的核心公式如下

折半查找

$mid = \frac{low + high}{2}$
插值查找

$mid = low + \frac{key - a[low]}{a[high] - a[low]} \left( high - low\right)$
斐波那契查找

$mid = low + F[k-1] - 1$

线性索引查找

索引就是把一个关键字与它对应的记录相关联的过程。所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。常见的线性索引分为：稠密索引、分块索引、倒排索引。

稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项
分块索引是把数据集的记录分成了若干块
倒排索引即通过属性值来确定记录的位置

参考文献：

大话数据结构