第5章查找of北京联合大学数据结构.pdf

目录 • 第一章基本概念 • 第二章线性表 • 第三章栈和队列 • 第四章树和二叉树 • 第五章查找 • 第六章查找树 • 第七章排序 • 第八章图 王郁昕 第五章查找 折半查找 散列表（Hash Tables） 王郁昕 折半查找（Binary Search） • 是对有序表的查找方法 • 方法：先确定待查记录所在的范围(区间)， 然后逐步缩小范围，直到找到或找不到该 记录为止 王郁昕 折半查找的过程示意图 m = (low + high)/2 王郁昕 折半查找算法 BINARY-SEARCH(A, key) 1 low = 1 2 high = A . length 3 while low = high 4 m = (low + high)/2 5 if key== A[m] 6 return m 7 if key A[m] 8 high=m- 1 9 else low=m+ 1 10 return -1 结束条件: low high 王郁昕 结束情况 结束条件: low high 王郁昕 5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92 key=21 5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92 5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92 5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92 5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92 key=22 (lowhigh) key=80 5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92 5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92 王郁昕 折半查找与BST树（判定树） • 由于m = (low + high)/2的约束，可以将任一有序序列看 成是一颗BST树(也称为“判定树”)，每个m对应于树中 的一个结点，首个m对应于树根。 • 显然折半查找判定树是平衡的。 王郁昕 折半查找树的性质 • 是一颗BST树 • 是一颗AVL树 • 不平衡的结点只可能出现在倒数第二层 • 除了最低层以外其他每层都满足：每层的 结点个数=2i-1 ，其中i表示层数 • 折半查找树的树高h= log N＋1 2 王郁昕 典型题 • 已知有序序列长度N • 求：找到给定key时最少查找次数 • 求：找到给定key时最多查找次数 • 求：找不到给定key时最少查找次数 • 求：找不到给定key时最多查找次数