计算机程序设计中查找算法的效率分析

摘要：查找是计算机程序设计中的核心操作，查找算法的效率对程序开发起着至关重要的影响。顺序查找、折半查找、分块查找和哈希查找四种查找方法及效率被详细分析，根据查找表中关键字的特点选择合适的查找方法，可以提高程序的效率。

关键词：查找；哈希函数；程序设计；查找表；

Abstract: Search is the core operation in computer programming design,search algorighm efficiency has important influence on program develop.Sequential search,binary search,block search and hash serach four kinds of search methods and efficiency are analyzied in detail.Selecting appropriate search method according to the character of keywords in search table can improve program efficiency.

Key words:search;hash function;programming design;search table

[中图分类号] TP31 [文献标识码]A[文章编号]

查找是人们日常生活中经常涉及的操作之一，比如查找电话簿中某个单位的电话号码，在词典中查找某个单词的含义等等。为了方便人们的操作，许多信息管理系统随之而开发，诸如图书查询系统、列车时刻表、成绩查询系统、药品管理系统等，查询是信息管理系统的核心操作，大约占数据库操作量的60%[1]。查找算法的设计对于整个程序的效率起着至关重要的影响。本文针对计算机程序设计中经常采用的查找算法进行了深入的分析，对其效率进行了细致的对比。为了简化起见，下文中的查找表是指要查找的记录集合，关键字是指用来唯一标识一条记录的数据项，比如居民身份信息中的身份证号码，图书信息中的ISBN号等。

1顺序查找

顺序查找是最为简单的一种查找方法，其基本原理为：将待查找记录的关键字和查找表中记录的关键字逐一比较，可以从表头到表尾，也可以从表尾一直向前到表头[2]。两种结果：一种是查找到某个位置时，找到了所要找的记录，我们说查找成功；另一种是直到查找到表的一端，也未发现要找到的记录，我们说查找失败，换句话说，查找表中没有要查找的记录。图1所示是顺序查找的一个子函数，该函数在学生成绩记录查找表中查找是否存在一个学号和K相等的学生，如果存在，输出该学生的学号和成绩；否则，输出无此记录的提示信息，通过这个函数我们可以理解顺序查找的思想及方法。

通过对程序时间复杂度分析，其时间复杂度T(n)=O(n),在顺序查找中，若找到所要的记录，需平均比较（N+1）/2次，N为查找表中记录的个数，也就是说，需要平均比较表长的一半左右才能查找成功，效率不是很高，但方法非常简单，易于实现。

2折半查找

折半查找又叫二分查找，其基本思想是将待查找记录的关键字K首先和查找表中中间位置记录的关键字相比较，如果相等，查找成功；如果K较小，则在查找表的前半个子表中继续折半查找；如果K较大，则在查找表的后面半个子表中继续折半查找。因为每经过一次比较，查找范围都缩小了一半，所以被叫做折半查找。

举例来说，查找表中记录的关键字为（15，23，35，46，58，77，88），N=7，待查找的记录关键字为77，如果采用顺序查找，从表头开始，需比较6次才能找到；若采用折半查找，首先将77和表中中间位置也就是第4个位置上记录的关键字46相比，因为77较大，所以将查找范围缩小到（58，77，88）后半个子表中，77继续和中间位置记录的关键字相比，二者相等，两次比较后查找成功。其相应的实现算法如图2所示。

从以上的分析中我们可以看出，折半查找只适用于表中记录关键字有序排列的情况，且查找表必须采用顺序存储结构，因其具有随机存储的特点。通过算法我们可以分析出，在折半查找中，若找到所要的记录，需大约平均比较log2（N+1）-1次，效率非常高。

3分块查找

分块查找是顺序查找的一种改进[3]，该方法要求查找表满足“分块有序”的特点：查找表中记录按关键字分成若干子表，后一子表中记录的关键字均大于前一子表中所有记录的关键字的值，但每一子表中记录的关键字不要求有序。另外，除了查找表之外，还需建立一个索引表，存储每个子表中的最大关键字及起始位置，表结构如图3所示。

图3查找表及索引表

查找分块查找时，先根据每个子表中的最大关键字值查找索引表确定待查找记录所在的子表，然后根据子表中第一个记录位置顺序查找该子表。索引表中每个索引项是有序排列的，所以对索引表可折半查找，对确定的子表顺序查找，是前面两种查找方式很好的结合，在很大程度上提高了查找效率，其平均查找长度为log2（N/s +1）+s/2,s 为每个子块含有的记录数目。

4 哈希查找

哈希查找是利用哈希函数实现的一种查找方法。哈希函数是在记录的关键字和记录的存储位置之间建立一种对应关系，这种对应关系我们称之为哈希函数[4]。哈希函数的构造很灵活，常见的构造方法有；直接定址法、数字分析法、平方后取中值、折叠法、除留余数法、随机函数法等，也可以根据查找表中记录关键字的具体分布自行设定。对于哈希函数，冲突是不可避免的，即对于不同的关键字，得到相同的哈希地址。相应的处理冲突方法有：开放定址法、再造哈希法、链地址法和建立一个公共溢出区。对于哈希查找，理想的情况是平均查找长度为0，对于一个给定的待查找记录关键字，只要用哈希函数计算出记录的存储位置，直接提取出相应的记录即可。但是由于冲突的存在，达不到理想的状态。当采用开放定址法中的线性探测再散列处理冲突时，平均查找长度为（1+1/(1-b)）/2；当采用随机探测再散列处理冲突时，平均查找长度为-ln(1-b)/b；当采用链地址法处理冲突时，平均查找长度为1+b/2,b是装填因子，即表中填入的记录数和哈希表长度的比值。对于哈希查找，只要哈希函数分布比较均匀，能大大提高查找效率。

5 结论

计算机程序设计中查找是出现频度非常高的算法之一，查找算法的设计对于整个程序的效率起到至关重要的影响。可以根据查找表中记录的关键字分布选取合适的查找方法。如果表的长度不是很长且无序排列，可以选择顺序查找；如果是一个有序表且查找表以顺序存储结构存储，折半查找是一个不错的选择；如果查找表符合“分块有序”的特征，可以进行分块查找；如果记录的关键字和存储位置可以建立一个分布均匀的函数关系，可以选择哈希函数。总之，查找方法的选择可以在很大程度上提高人们的查找效率。

参考文献：

[1]朱如龙. SQLServer数据库应用系统开发技术[M].北京：机械工业出版社，2008.

[2]严蔚繁,吴伟民.数据结构（C语言版）[M].北京：清华大学出版社.2008

[3]严蔚繁,陈文博.数据结构及应用算法教程[M]. 北京：清华大学出版社.2011

[4]赵彦.数据库原理与应用技术开发[M].北京：清华大学出版社.2009

作者简介：

王哲，男，汉族，1983年9月出生，2006年7月毕业于沈阳理工大学计算机科学与技术专业，学士，目前在中国石油锦西石化分公司信息管理部工作，助理工程师。

注：文章内所有公式及图表请用PDF形式查看。