|
|
|
静态查找的算法有顺序查找、折半查找、分块查找和静态树查找等，其中顺序表上的顺序查找、折半查找是静态查找的重点。被查找的顺序表C类型定义如下：
|
|
|
|
|
|
|
|
顺序查找的基本思想是：从表中第n个（第1个）记录开始，逐个进行记录的关键字与给定值的比较，若某个记录的关键字与给定值比较相等，则查找成功，找到所查记录；反之，若直到第1个（第n个）记录，其关键字与给定值比较都不等，则表明该表中没有所查的记录，查找不成功。
|
|
|
|
|
|
|
|
可见，在查找中与关键字的比较次数ci取决于所查记录在表中的位置，如查找表中第n个记录，仅需要比较1次；而查找表中第1个记录时，需要比较n次，即ci=n-i+1。因此，在等概率的情况下，成功查找时的顺序查找的平均查找长度为：
|
|
|
|
|
|
即查找成功时的平均比较次数约为表长的一半。若k值不在表中，则需要进行n+1次比较才能确定查找失败。
|
|
|
|
|
|
若顺序表中元素已按关键字有序排列，检索时不必顺序检索，而是用待查关键字与中间位置的元素的关键字进行比较，若相等，则检索成功；若待查关键字较小，则在由中间位置分开的左子表中查找，否则，在右子表中进行查找。如此下去，直至检索成功或检索失败。
|
|
|
|
|
|
|
|
折半查找的过程可用二叉树来描述，中间结点是二叉树的根，左子表相当于左子树，右子表相当于右子树，由此得到的二叉树便为描述折半查找的判定树。折半查找的过程是走了一条从根结点到叶子结点的过程，不论检索成功与失败，查找长度均不超过树的高度，其平均性能为h=[log2(n+1)]。
|
|
|
|
折半查找速度快，但表必须有序，且频繁插入和删除不方便。它适合表中元素很少变化而检索频繁的情况；顺序表检索适用于检索少而表中元素频繁变化的情况。
|
|
|
|
|
|
分块查找综合了顺序查找和折半查找的优点，既有动态结构，又适于快速查找。分块查找的基本思想是：将待查找文件等长地分为若干个子文件（最后一个子文件长度可能会小）。子文件内的元素无序，但子文件之间有序，即第一个子文件的最高关键字小于第二个子文件的所有记录的关键字，第二个子文件的最高关键字小于第三个子文件的所有记录的关键字，依次类推。再建立一个索引表（文件），文件中的每个元素含有各个子文件的最高关键字和各个子文件中第一个元素的地址（下标），索引文件按关键字有序。
|
|
|
|
分块查找过程分两步：第一步是在索引表中确定待查记录所在的块，可以顺序查找或折半查找；第二步是在块内顺序查找。
|
|
|
|
设待检索文件有n个记录，平均分成b块，每块有s个记录。若只考虑检索成功的概率，且在块内和索引表中均用顺序检索，则平均查找长度为：
|
|
|
|
|
|
其中，Lb为确定块的平均查找长度；Lw为块内查找次数。
|
|
|
若s= ，则平均查找长度取最小值： +1。
|
|
|
|
|
|
|
