顺序查找和折半查找

顺序查找

顺序查找又称线性查找，主要用于在线性表中进行查找。顺序查找通常分为对一般的无序线性表的顺序查找和对按关键字有序的顺序表的顺序查找。下面分别进行讨论。

一般线性表的顺序查找

作为一种最直观的查找方法，其基本思想是从线性表的一端开始，逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足给定条件，则查找成功，返回该元素在线性表中的位置；若已经查找到表的另一端，但还没有查找到符合给定条件的元素，则返回查找失败的信息。下面给出其算法，主要是为了说明其中引入的“哨兵”的作用。

typedef struct {   // 查找表的数据结构（顺序表）
    int *elem;     // 动态数组基址
    int TableLen;  // 表的长度
} SSTable;
// 顺序查找
int Search_Seq(SSTable ST, int key) {
    ST.elem[0] = key;  // "哨兵"，存放在数组索引0的位置
    int i;
    for (i = ST.TableLen; ST.elem[i] != key; --i) {  // 从后往前找
        return i;  // 查找成功，则返回元素下标；查找失败，则返回0
    }
}

在上述算法中，将 ST.elem[0] 称为“哨兵”。引入它的目的是使得 Search_ Seq 内的循环不必判断数组是否会越界，因为满足 i==0 时，循环一定会跳出。需要说明的是，在程序中引入“哨兵”并不是这个算法独有的。引入“哨兵”可以避免很多不必要的判断语句，从而提高程序效率。

对于有 个元素的表，给定值 key 与表中第 个元素相等，即定位第 个元素时，需进行 次关键字的比较，即 。查找成功时，顺序查找的平均长度为 当每个元素的查找概率相等，即 时，有： 查找不成功时，与表中各关键字的比较次数显然是 次，从而顺序查找不成功的平均查找长度为 。

通常，查找表中记录的查找概率并不相等。若能预先得知每个记录的查找概率，则应先对记录的查找概率进行排序，使表中记录按查找概率由小至大重新排列。

综上所述，顺序查找的缺点是当 较大时，平均查找长度较大，效率低；优点是对数据元素的存储没有要求，顺序存储或链式存储皆可。对表中记录的有序性也没有要求，无论记录是否按关键字有序，均可应用。同时还需注意，对线性的链表只能进行顺序查找。

有序表顺序查找

若在查找之前就已经知道表是关键字有序的，则查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度。

假设表 L 是按关键字从小到大排列的，查找的顺序是从前往后，待查找元素的关键字为 key，当查找到第 个元素时，发现第 个元素对应的关键字小于 key，但第 个元素对应的关键字大于 key，这时就可返回查找失败的信息，因为第 个元素之后的元素的关键字均大于 key，所以表中不存在关键字为 key 的元素。

可以用查找判定树来描述有序顺序表的查找过程。树中的圆形结点表示有序顺序表中存在的元素；树中的矩形结点称为失败结点（若有 个结点，则相应地有 个查找失败结点），它描述的是那些不在表中的数据值的集合。若查找到失败结点，则说明查找不成功。

在有序表的顺序查找中，查找成功的平均查找长度和一般线性表的顺序查找一样。查找失败时，查找指针一定走到了某个失败结点。这些失败结点是我们虚构的空结点，实际上是不存在的，所以到达失败结点时所查找的长度等于它上面的一个圆形结点的所在层数。查找不成功的平均查找长度在相等查找概率的情形下为：

式中， 是到达第 个失败节点的概率，在相等查找概率的情况下，它为 ； 是第 个失败结点所在的层数。

注意，有序表的顺序查找和后面的折半查找的思想是不一样的，且有序表的顺序查找中的线性表可以是链式存储结构。

折半查找

折半查找又称二分查找，它仅适用于有序的顺序表。

折半查找的基本思想：首先将给定值 key 与表中中间位置的元素比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分（例如，在查找表升序排列时，若给定值 key 大于中间元素，则所查找的元素只可能在后半部分）。然后在缩小的范围内继续进行同样的查找，如此重复，直到找到为止，或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。算法代码实现如下：

int Binary_Search(SeqList L, ElemType key) { // 升序排列
    int low = 0, high = L.TableLen - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2;  // 取中间位置
        if (L.elem[mid] == key) {
            return mid;  // 查找成功则返回所在位置
        } else if (L.elem[mid] > key) {
            high = mid - 1;  //从前半部分继续查找}
        } else {
            low = mid + 1;  // 从后半部分继续查找
        }
        return -1;  // 查找失败，返回-1
    }
}

折半查找的过程可用二叉树来描述，称为判定树。树中每个圆形结点表示一个记录，结点中的值为该记录的关键字值；树中最下面的叶结点都是方形的，它表示查找不成功的情况。

从判定树可以看出，查找成功时的查找长度为从根结点到目的结点的路径上的结点数，而查找不成功时的查找长度为从根结点到对应失败结点的父结点的路径上的结点数；每个结点值均大于其左子结点值，且均小于于其右子结点值。若有序序列有 个元素，则对应的判定树有 个圆形的非叶结点和 个方形的叶结点。显然，判定树是一棵平衡二叉树。

由上述分析可知，用折半查找法查找到给定值的比较次数最多不会超过树的高度。在等概率查找时，查找成功的平均查找长度为：

式中， 是树的高度，并且元素个数为 时树高

所以，折半查找的时间复杂度为 #card=math&code=O%28%5Clog_%7B2%7D%7Bn%7D%29&id=peV3F)，平均情况下比顺序查找的效率高。

因为折半查找需要方便地定位查找区域，所以它要求线性表必须具有随机存取的特性。因此，该查找法仅适合于顺序存储结构，不适合于链式存储结构，且要求元素按关键字有序排列。

分块查找

分块查找又称索引顺序查找，它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找。

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

// 索引表
typedef struct{
    ElemType maxValue;
    int low,high;
}Index;
// 顺序表存储实际元素
ElemType List[100];

分块查找的过程分为两步：

1. 在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表；
2. 在块内顺序查找。

若索引表中不包含目标关键字，则折半查找索引表最终停在 low > high 要在 low 所指分块中查找。原因是最终 low 左边一定小于目标关键字，high 右边一 定大于目标关键字。而分块存储的索引表中保存的是各个分块的最大关键字。

分块查找的平均查找长度为索引查找和块内查找的平均长度之和。设索引查找和块内查找的平均查找长度分别为 ，，则分块查找的平均查找长度为： 将长度为 的查找表均匀地分为 块，每块有 个记录，在等概率情况下，若在块内和索引表中均采用顺序查找，则平均查找长度为：

此时，若 ，则平均查找长度取最小值 ；若对索引表采用折半查找时，则平均查找长度为：

%7D%20%5Cright%20%5Crceil%2B%5Cfrac%7Bs%2B1%7D%7B2%7D#card=math&code=ASL%3DL1%2BL_2%3D%20%5Cleft%20%5Clceil%20%5Clog%7B2%7D%7B%28b%2B1%29%7D%20%5Cright%20%5Crceil%2B%5Cfrac%7Bs%2B1%7D%7B2%7D&id=jKMkR)$