North China Electric Power University I 递归算法描述如下 Procedure Bin Search(r:stAble, k KeyType, l, h: Integer); Begin low: =l high: =h if high<low then write Unsucc); Return; mid:(lowthigh) div 2; Case krmid]. key: [low:=mid+l; Bin Search(r,,low,high); krlmid key: write(mid); Return; I k<rlmid key: high: =mid-1; Bin Search(r, k,low, high) End Case End:
North China Electric Power University Procedure BinSearch(r:sqTable;k:KeyType,l,h:Integer); Begin low:=l; high:=h; if high<low then [Write(‘Unsucc’);Return;] mid:=(low+high) div 2; Case k>r[mid].key: [low:=mid+1;BinSearch(r,k,low,high); k=r[mid].key: [Write(mid);Return;] k<r[mid].key: [high:=mid-1;BinSearch(r,k,low,high); EndCase; End; 递归算法描述如下：
North China Electric Power University I 算法的性能分析: 以上面的11个元素的查找表为例,找到第6个元素仅需比较1次; 找到第3个和第9个元素需比较次;找到第14,7和10个元素需比较 3次;找到第2,5,8和11个元素需比较4次。上面的查找过程可以用 下图所示的一棵二叉树来表示。 6 树中每一个结点表 示表中的一个数据 3 元素,结点中的值 9 为该元素在表中的 位置 4 7 10 2 5 8 折半查找的平均查找长度为bg(+)1
算法的性能分析： North China Electric Power University 以上面的11个元素的查找表为例，找到第6个元素仅需比较1次； 找到第3个和第9个元素需比较2次；找到第1,4,7和10个元素需比较 3次；找到第2,5,8和11个元素需比较4次。上面的查找过程可以用 下图所示的一棵二叉树来表示。 6 3 9 1 4 7 10 2 5 8 11 树中每一个结点表 示表中的一个数据 元素，结点中的值 为该元素在表中的 位置 折半查找的平均查找长度为log2 (n+1)-1
North China Electric Power University I 找不到元素的过程:正好是从根节点一直走到某个 叶子节点的路径,因此所用的比较次数最多等于树的深 度。由此看来,无论元素找到或找不到查找某一元素 的比较次数最多等于树的深度.即10gn。 那么引出一个问题,折半查找的平均查找长度是多少? 我们用深度为h的满二叉树描述折半查找来进行分析。 满二叉树的特点是: 层次为1的结点有1个; 层次为2的结点有2个; 层次为h的结点为2h1个 若是完全二叉树则节点数n=2h-1 那么表的长度一定为n=2h-1,我们假定表中每个元素的 查找概率相等.(Pi=1/n),则平均查找长度为 ASLns=2CiPi-1 9 j*21-1(+1/)*log2(n+1)1A
找不到元素的过程：正好是从根节点一直走到某个 叶子节点的路径，因此所用的比较次数最多等于树的深 度。由此看来，无论元素找到或找不到,查找某一元素 的比较次数最多等于树的深度.即 log2n 。 那么引出一个问题，折半查找的平均查找长度是多少? 我们用深度为h的满二叉树描述折半查找来进行分析。 满二叉树的特点是： 层次为1的结点有1个; 层次为2的结点有2个; …, 层次为h的结点为2 h-1 个 。 若是完全二叉树则节点数n=2 h -1 那么表的长度一定为n=2 h-1,我们假定表中每个元素的 查找概率相等.(Pi=1/n),则平均查找长度为: ASLnS=∑CiPi=1/n∑j*2j-1 i=1 n j=1 n =(n+1/n)*log2 (n+1)-1 North China Electric Power University
North China Electric power University 3)分块查找这种查找方法是表里的元素均匀的分 成若干块,块与块之间是有序的,块中的元素 是无序的,这种查找方法又称为索引顺序查找。 在分块查找中对每一块建立一个索引项,其中包括两项 内容:关键字项(其值为最大关键字或最小关键字)和指 针项(指示该块的第1个记录在表中的位置)。索引表按 关键字有序,表分块有序。 分块有序:指第二块中所有记录的关键字均大于(或小于) 第一块中最大(或最小)关键字,第三块中的所有关键字均 大于(或小于)第二块中的最大(或最小关键字…以此类推 例:有一个表,各元素的关键字为 22,12,13,9,8,33,42,44,38,24,48,60,58,74,47} 把它平均分成三块,按上升的次序排列,如下图所示:
North China Electric Power University 3)分块查找:这种查找方法是表里的元素均匀的分 成若干块，块与块之间是有序的，块中的元素 是无序的，这种查找方法又称为索引顺序查找。 在分块查找中对每一块建立一个索引项，其中包括两项 内容：关键字项(其值为最大关键字或最小关键字)和指 针项(指示该块的第1个记录在表中的位置)。索引表按 关键字有序，表分块有序。 分块有序：指第二块中所有记录的关键字均大于(或小于) 第一块中最大(或最小)关键字，第三块中的所有关键字均 大于(或小于)第二块中的最大(或最小)关键字…,以此类推。 例:有一个表,各元素的关键字为: ｛22,12,13,9,8,33,42,44,38,24,48,60,58,74,47} 把它平均分成三块，按上升的次序排列，如下图所示：
North China Electric Power University I 2|12 指针表应该指向各块的第一个关键字。 第一块 3|13 8 关键字表 6|33 22 742 分成三块 第二块 8|44 44 每块5个 938 1174 大天键字 1148 12|60 第三块 13158 4|74 分块查找的方法 1)由于索引表按关键字有序,则确定k在哪一块的查找 可以用顺序查找,也可用折半查找
North China Electric Power University 22 12 13 9 8 33 42 44 38 24 48 60 58 74 47 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 第一块 第二块 第三块 1 6 11 22 44 74 关键字表 小 大 指针表:应该指向各块的第一个关键字。 分成三块 每块5个 关键字 分块查找的方法: 1)由于索引表按关键字有序，则确定k在哪一块的查找 可以用顺序查找，也可用折半查找