以11个数的查找为例 513192137566475808892 性能分新 1234567891011 找到第6个数仅需比较次,查找某个结点所比较的次数等于该 找到第3和第9个数需2次,结点的层次数加1。 找到第1,4,7,10个数需3次, 找到第258和1个数需4次。查找某个结点的过程就是从根结点 查我过程用二又树来表示到相应的结点的路径。 查找成功时进行比较的次数最多不超过该树的深度。 具有n个结点的判定树的深度为 logon ·折半查找法在查找成功时比较次数最多为10gn次。 查找不成功的情况如下所示(方框表示查找不成功的情况) 少⑥查找不成功时的最多比较次数也是 llog nh+1 2)(5(8 s67③910 L46四88⑩
折半量的平跑量属 先看一个具体的情况,假设:m=11 i1234567891011 C;34234134234 判定树 6 3 9 7 10 5 8
一般情况下,表长为n的折半查找的判定树的深 度和含有n个结点的完全二叉树的深度相同。 假设n=2-1并且查找概率相等则 AS=∑c=∑j 211/_n+1 log(n+1)-1 i=1 在n>50时可得近似结果AS≈log(On+1)-1 优点:比较次数少,检索速度快. 缺点:字典按关键码排序,只适用于顺序存储结构
log ( 1) 1 1 2 1 1 2 1 1 1 n n n j n C n ASL h j j n i bs i log ( 1) 1 ASLbs 2 n
三、分块宣找(泰引顺序查找) 这是一种顺序查找的另一种改进方法。 1.先让数据分块有序,即分成若干子表,要求每个子表 中的数值(用关键字更准确)都比后一块中数值小(但 子表内部未必有序) 2.然后将各子表中的最大关键字构成一个索引表,表中 还要包含每个子表的起始地址(即头指针)。 例: 特点:块间有 最大关键字[24886 序,块内无序 起始地扯1713 2212138920334244382448605874498653 第1块 第2块 第3块
分块查找 桑引顺序 在建立顺序表的同时,建立一个索引。 例如:顺序表 012345678910111213。。。 17082119143133222540526178|46. 索引「2104057810 ●。●● 索引顺序表=索引+顺序表