7.1.2　静态查找表

1. 顺序查找

(1) 查找过程。从查找表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定的值比较相等，则查找成功，找到所查记录；反之，不相等则查找不成功。

(2) 适用条件。不要求记录按关键字有序且能应用于顺序存储和链式存储。

(3) 平均查找长度为O(n)。

2. 折半查找

(1) 折半查找(二分查找)。将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

(2) 查找条件：表中的数据必须是有序的。

(3) 查找深度为[log₂n]+1。

3. 索引顺序表的查找

(1) 索引顺序表的查找(分块查找)。把线性表分成若干块，每一个块中的元素存储顺序是任意的，块之间按关键字大小有序排列，前一个块的最大关键字大于后一个块的最小关键字；还需确定一个索引表，它的每一项对应线性表中的一块。

(2) 查找过程。先通过索引表查找块(可采用折半查找)，再在块中用顺序查找表的方法去查找。