插值查找

插值查找，有序表的一种查找方式。插值查找是根据查找关键子与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找，将查找点的选择改进为自适应选择，提高查找效率。

基本思想查找( Search)是指从一批记录中找出满足指定条件的某一记录的过程，查找又称为检索。查找算法广泛应用于各类应用程序中。因此，一个有效的查找算法往往可以大大提高程序的执行效率。在实际应用中，数据的类型千变万化，每条数据项往往包含多个数据域。但是，在执行查找操作时，往往只是指定一个或几个域的值，这些作为查找条件的域称为关键字(Key)，关键字分为两类。

我们遇到的大部分查找问题都是以主关键字为准的。而且为了方便读者的理解，后面将以整型数据关键字为例进行讲解，其他类型的关键字的查找算法与此类似。如果查找到相应的数据项，往往需要返回该数据项的地址或者位置信息。这样程序中即可通过位置信息来进行显示数据项、插入数据项、删除数据项等操作。如果没有查找到相应的数据项，则可以返回相应的提示信息。

在实际应用中，针对不同的情况往往可以选择不同的查找算法。对于无顺序的数据，只有逐个比较数据，才能找到需要的内容，这种方法称为顺序查找。对于有顺序的数据，也可以采用顺序查找法逐个比较，但也可以采取其他更快速的方法找到所需数据。另外，对于一些特殊的数据结构，例如链表、树结构和图结构等，也都有相对应的合适的查找算法。1

插值类似于平常查英文字典的方法，在查一个以字母C开头的英文单词时，决不会用二分查找，从字典的中间一页开始，因为知道它的大概位置是在字典的较前面的部分，因此可以从前面的某处查起，这就是插值查找的基本思想。

插值查找除要求查找表是顺序存储的有序表外，还要求数据元素的关键字在查找表中均匀分布，这样，就可以按比例插值。2

性能分析插值查找性能分析：算法在最好和最坏情况下的关键字比较次数是明显的，但平均情况的分析比较复杂，并且这里的“平均”与前面讨论过的查找算法的平均不同，这里是在元素满足某种分布情况下的平均。3

适用条件适合于关键字值分布均匀的集合。

应用根据关键字的分布估计被查元素的位置，能更精确定位到被查找元素的位置，但应用有限。4

其他查找算法分块查找若查找表中的数据元素的关键字是按块有序的，则可以做分块查找。分块查找又称索引顺序查找，是对顺序查找的一种改进。分块查找将查找表按块分成若干个子表，对每个子表建立一个索引项，再将这些索引项顺序存储，形成一个索引表。每个索引项包括两个字段：关键码字段（存放对应子表中的最大关键码值）和指针字段（存放指向对应子表的指针），这样索引表则是按关键码有序的。查找时，分成两步进行：先根据给定值kx在索引表中查找，以确定所要查找的数据元素属于查找表中的哪一块，由于索引表按关键码有序，因此可用顺序查找或折半查找；然后，再进行块内查找，因为块内无序，只能进行顺序查找。2

顺序查找顺序查找比较简单，执行的操作是从数据序列中的第1个元素开始，从头到尾依次逐个查找，直到找到所需要的数据或搜索整个数据序列。顺序查找主要针对数量较少的、无规则的数据。对于包含n个数据的数据序列，使用顺序查找方法查找数据，最理想的情况是目标数据位于数组的第1个，这样比较1次就能找到目标数据;而最差的情况是需要比较完所有的n个数据才能找到目标数据或者确认没有该数据。平均来说，使用顺序查找方法比较次数为n2次，效率是比较低的。1

本词条内容贡献者为:

徐恒山 - 讲师 - 西北农林科技大学