【软考-软件设计师精华知识点笔记】第八章 算法分析设计

折半（二分）查找：前提是数据要按照递增/递减排好序

设查找表的元素存储在一维数组r[1..n]中，在表中元素已经按照关键字递增方式排序的情况下，进行折

半查找的方法是：

1、首先将待查元素的关键字（key）值与表r中间位置上（下标为mid)记录的关键字进行比较，若相

等，则查找成功；

2、若key>r[mid].key，则说明待查记录只可能在后半个子表r[mid+1..n]中，下一步应在后半个子表

中查找；

3、若key<r[mid].key，说明待查记录只可能在前半个子表r[1..mid-1]中，下一步应在r的前半个子表

中查找；

的比较才能确定被查记录在表中的位置。也就是说，这类查找都是以关键字的比较为基础的，而哈希

表则通过一个以记录的关键字为自变量的函数（称为哈希函数）得到该记录的存储地址，所以在哈希

表中进行查找操作时，需要用同一哈希函数计算得到待查记录的存储地址，然后到相应的存储单元去

获得有关信息再判定查找是否成功。

散列（哈希）表：根据设定的哈希函数H（key)和处理冲突的方法，将一组关键字映射到一个有限的连

续的地址集上，并以关键字在地址集中的“像”作为记录在表中的存储位置。

在上图中，很明显，哈希函数产生了冲突，使用的是线性探测法解决冲突，还有其他方法如下：

线性探测法：按物理地址顺序取下一个空闲的存储空间。

伪随机数法：将冲突的数据随机存入任意空闲的地址中。