散列查找

Low指向待查元素 所在区间的下界 mid指向待查元素所在 区间的中间位臵 high指向待查元素所 在区间的上界
解：① 先设定3个辅助标志: low,high,mid， 显然有：mid= (low+high)/2 ② 运算步骤：
(1) low =1,high =11 ,故mid =6 ，待查范围是 [1,11]； (2) 若 S[mid] < key，说明 key[ mid+1,high] ， 则令：low =mid+1;重算 mid＝ (low+high)/2；. (3) 若 S[mid] > key，说明key[low ,mid-1]， 则令：high =mid–1;重算 mid ； (4)若 S[ mid ] = key，说明查找成功，元素序号=mid; 结束条件： （1）查找成功 ： S[mid] = key （2）查找不成功 ： high＜low （意即区间长度小于0）
while(low<=high)
{ mid=(low+high)/2; if(ST[mid].key= = key) return (mid); /*查找成功*/
else if( key< ST[mid].key) high=mid-1; /*在前半区间继续查找*/ else } return (0); /*查找不成功*/
4 5 6 7
0
1
2
90
10
(c)
20
40
K=90
80
30
60
Hale Waihona Puke 25(return i=0 )
6
讨论：怎样衡量查找效率？
——用平均查找长度（ASL）衡量。
如何计算ASL？

第26页，共32页。
例8-6 以{14,1,68,27,55,23,11,10,19,20,79,84} , 构造 hash表。hash表长度为17, hash(key)=key % 17。
解决冲突——公共溢出区。
hash 表：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
27
10
11
79
14
84 第18页，共32页。
二、开放定址法
当冲突发生时，使用某种方法在散列表 中形成一个探查序列，沿着此序列逐个地址 去探查，直到找到一个开放的地址（空位 置），将发生冲突的键值放到该地址中。 （1）线性探查法 （2）二次探测法 （3）再散列探查法。
第19页，共32页。
（1）线性探测法
n （d+h2(k))%m,
n （d+2h2(k))%m,
n （d+3h2(k))%m,
n ……..
h2的选取方法为：
若m为素数：h2(k)=k%(m-2)+1 若m为2i：h2(k)=1～m-1之间的任一奇数。 （这样总保证使h2(k)和m互质）。
第25页，共32页。
三、公共溢出区法
对具有相同散列地址的记录，将第1个放在 hash表中，其余的都存储在同一个溢出区 中。
体，并从中提取分布均匀的若干位或它们的组合 作为地址。
参见教材 P278
仅限于：能预先估计出全体关键字的每一位
上各种数字出现的频度。
第9页，共32页。
（3）平方取中法
若关键字的每一位都有某些数字重复出现频度
很高的现象，则先求关键字的平方值，以通过“平方” 扩大差别，同时平方值的中间几位受到整个关键字中

本资料由理硕教育整理，理硕教育是全国唯一专注于北理工考研辅导的学校，相对于其它机构理硕教育有得天独厚的优势。

丰富的理工内部资料资源与人力资源确保每个学员都受益匪浅，确保理硕教育的学员初试通过率89%以上，复试通过率接近100%，理硕教育现开设初试专业课VIP一对一，初试专业课网络小班，假期集训营，复试VIP一对一辅导，复试网络小班，考前专业课网络小班，满足学员不同的需求。

因为专一所以专业，理硕教育助您圆北理之梦。

详情请查阅理硕教育官网第 7 章查找技术课后习题讲解1. 填空题⑴顺序查找技术适合于存储结构为（）的线性表，而折半查找技术适用于存储结构为（）的线性表，并且表中的元素必须是（）。

【解答】顺序存储和链接存储，顺序存储，按关键码有序⑵设有一个已按各元素值排好序的线性表，长度为125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（）次，至多需比较（）次。

【解答】1，7【分析】在折半查找判定树中，查找成功的情况下，和根结点的比较次数最少，为1次，最多不超过判定树的深度。

⑶对于数列{25，30，8，5，1，27，24，10，20，21，9，28，7，13，15}，假定每个结点的查找概率相同，若用顺序存储结构组织该数列，则查找一个数的平均比较次数为（）。

若按二叉排序树组织该数列，则查找一个数的平均比较次数为（）。

【解答】8，59/15【分析】根据数列将二叉排序树画出，将二叉排序树中查找每个结点的比较次数之和除以数列中的元素个数，即为二叉排序树的平均查找长度。

⑷长度为20的有序表采用折半查找，共有（）个元素的查找长度为3。

【解答】4【分析】在折半查找判定树中，第3层共有4个结点。

⑸假定一个数列{25，43，62，31，48，56}，采用的散列函数为H(k)=k mod 7，则元素48的同义词是（）。

【解答】62【分析】H(48)= H(62)=6⑹在散列技术中，处理冲突的两种主要方法是（）和（）。

18个查找函数-回复查找函数在计算机编程中是非常重要的工具，它们可以帮助我们在大量的数据中快速准确地找到所需的信息。

无论是对于数据分析、软件开发还是数据库管理，查找函数都是必不可少的。

本文将介绍18个常见的查找函数，并详细解释它们的功能和使用方法。

1. 线性查找（Linear Search）线性查找是最简单的一种查找方法，它从数据结构的一端开始逐个比较数据元素，直到找到目标元素或查找完整个数据结构。

如果数据结构是有序的，则可以使用二分查找等更高效的方法。

2. 二分查找（Binary Search）二分查找是一种针对有序数据结构的查找方法，它通过将待查找元素与数据中间位置的元素进行比较，从而将查找范围逐渐缩小一半，直到找到目标元素或确定不存在。

3. 插值查找（Interpolation Search）插值查找是一种改进的查找方法，它基于二分查找的思想，但是在选择比较元素时更加接近目标元素的位置。

这种方法适用于数据分布均匀的情况下，查找效率较高。

4. 哈希查找（Hash Search）哈希查找是一种基于哈希表实现的查找方法，它将关键字直接映射到哈希表的槽位上，从而能够在常数时间内快速定位目标元素。

这种方法适用于需要快速查找的场景。

5. 二叉查找树（Binary Search Tree）二叉查找树是一种经典的数据结构，它通过比较节点的值将数据分为左子树和右子树，并保持左子树节点的值小于根节点，右子树节点的值大于根节点。

在二叉查找树中进行查找操作时，可以根据节点值的大小关系选择下一步的查找方向。

6. 平衡二叉查找树（Balanced Binary Search Tree）平衡二叉查找树是在二叉查找树的基础上进行了平衡操作，以保持树的高度平衡，提高了查找的效率。

常见的平衡二叉查找树有红黑树和AVL树。

7. B树（B-Tree）B树是一种多路平衡查找树，它可以在每个节点中存储多个关键字和子节点，从而减少磁盘访问次数，提高查找效率。