算法研究：静态查找表

算法研究：静态查找表2013-08-21查找表（Search table）是由同一类型的数据元素（或记录）构成的集合。关键字（key）是数据元素中某个数据项的值，又称为键值，用它可以表示一个数据元素，也可以标识一个记录的数据项（字段），称之为关键码。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字（primary key）。而对于那些可以识别多个数据元素（或记录）的关键字，称为次关键字（Secondary Key），次关键字也可以理解为不以唯一标识一个数据元素（或记录）的关键字，它对应的数据项就是次关键码。

查找（Searching）就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

查找表按照操作方式来分有两大种：静态查找表和动态查找表。

静态查找表（Static Search Table）：只作查找操作的查找表，主要操作为：

（1）查询某个“特定的”数据元素是否在查找表中。

（2）检索某个 “特定的”数据元素和各种属性。

动态查找表（Dynamic Search Table）：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。

（1）查找时插入数据元素。

（2）查找时删除数据元素。

本文先来说说静态查找表。

一、顺序表查找

顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是：从表中的一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值都比较不相等时，则表中没有所查的记录，查找不成功。

二、有序表查找

1、折半查找

折半查找（ Binary Search）技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序（通常从小到大有序），线性表必须采用顺序存储。折半查找的基本思想是：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。

2、插值查找

插值查找（Interpolation Search）是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式（key-a[low]）/（a[high]-a[low]）。

3、斐波那契查找

斐波那契查找（Fibonacci Search）算法的核心在于

1）当key = a[mid] 时，查找就成功；

2）当key < a[mid] 时，新范围是第low 个到第mid - 1个，此时范围个数为F[k-1]-1个。

3）当key > a[mid] 时，新范围是第m+1 个到第 high个，此时范围个数为F[k-2]-1个。

如图8-4-13所示。