几种常见的查找算法

一、线性表的查找

1、顺序查找

顺序查找（Sequential Search）又称线性查找，它对顺序表和链表都是适用的。对于顺序表，可通过数组下标递增来顺序扫描每个元素；对于链表，可通过指针域来依次扫描每个元素。

查找表的数据结构如下：

typedef struct
{
    ElemType *elem; // 元素空间的基地址
    int length; // 表的长度
}SSTable;

顺序查找的算法如下：

int seq_search(SSTable st, ElemType key)
{
    int i;
    st.elem[0] = key; // 哨兵
    for(i = st.length; st.elem[i] != key; --i); // 从后向前找
    return i; // 若表中不存在关键字为key的元素，将查找到i为0时退出for循环
}

在上述算法中使用了一个“哨兵”，即st.elem[0]，目的是使得算法内的循环不必判断数组是否会越界。引入“哨兵”可以避免很多不必要的判断语句，从而提高程序的效率。

顺序查找的平均查找长度（Average Search Length, ASL）为：
$$
ASL = \frac{1}{n} \sum_{i=1}^{n}i = \frac{n+1}{2}
$$
时间复杂度为：
$$
T(n) = O(n)
$$
下面来说明顺序查找的优点和缺点：

优点：算法简单，对表结构无任何要求，既适用于顺序结构，也适用于链式结构，无论记录是否按关键字有序均可应用。
缺点：平均查找长度较大，查找效率较低，所以当 n 很大时，不宜采用顺序查找。

2、折半查找

详见《二分查找》

3、分块查找

分块查找（Blocking Search）又称索引顺序查找，这是一种性能介于顺序查找和折半查找之间的一种查找方法。在此查找法中，除表本身以外，尚需建立一个“索引表”，如下图所示。

分块查找的基本思想：将查找表分为若干块。块内的元素可以无序，但块之间是有序的，即第一个块中的最大关键字小于第二个块中的所有记录的关键字，第二个块中的最大关键字小于第三个块中的所有记录的关键字，以此类推。再建一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。

分块查找的过程分为两步：第一步是在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表；第二步是在表内顺序查找。由此可见，分块查找的算法顺序为顺序查找和折半查找两种算法的简单合成。

分块查找的平均查找长度为：
$$
ASL_{bs} = L_b + L_w
$$
其中，$L_b$为查找索引表确定所在块的平均查找长度，$L_w$为在块中查找元素的平均查找长度。

若用顺序查找确定所在块，则分块查找的平均长度为：
$$
ASL_{bs} = L_b + L_w = \frac{1}{b}\sum_{j=1}^{b}j+\frac{1}{s}\sum_{i=1}^{s}i = \frac{b+1}{2}+\frac{s+1}{2} = \frac{1}{2}(\frac{n}{s}+s)+1
$$
可见，此时的平均查找长度不仅和表长 n 有关，而且和每一块中的记录个数 s 有关。

若用折半查找确定所在块，则分块查找的平均查找长度为：
$$
ASL_{bs} \approx log_2(\frac{n}{s}+1)+\frac{s}{2}
$$
下面来说明分块查找的优点和缺点：