ASLnP, +(n-1)P2++2Pn-+P 设表中每个元素的查找概率相等Pn 则A=∑n=1=1.m+=+1 从上式可知,在不等概率査找的情况下, ASLSS在 Pn≥Pn位…≥P2≥P1时取极小值。 应对记录的查找概率进行排序,使表中记录按查找概率由 小到大重新排列,以便提高查找效率。 查找概率无法事先测定,则查找过程采取的改进办法是 在每次查找之后,将刚刚查找到的记录直接移至表尾的位 置上。 北京邮电大学自动化学院
北京邮电大学自动化学院 6 ASL = nP1 +(n-1)P2 + +2Pn-1+Pn 2 1 2 1 1 ( 1) 1 1 1 + = + = = = = = = n n n n i n ASL p c n p n i n i i i i 则 设表中每个元素的查找概率相等 ⚫ 从上式可知，在不等概率查找的情况下，ASLss 在 Pn≥Pn-1≥···≥P2≥P1时取极小值。 ⚫ 应对记录的查找概率进行排序，使表中记录按查找概率由 小到大重新排列，以便提高查找效率。 ⚫ 查找概率无法事先测定，则查找过程采取的改进办法是， 在每次查找之后，将刚刚查找到的记录直接移至表尾的位 置上
、顺序表的查找(顺序查找) 顺序查找的缺点是平均查找长度较大,特别是当n很大 时,查找效率低。然而,它有很大的优点是:算法简单且 适应面广。 当査找不成功时的情形不忽视时,査找算法的平均查找长 度应是查找成功时的平均查找长度与查找不成功时的平均 查找长度之和。 对于顺序查找,不论给定值key为何值,查找不成功时和 给定值进行比较的关键字个数均为n+1。假设查找成功与 不成功的可能性相同,对每个记录的查找概率也相等, 则P ,此时顺序查找的平均查找长度为 2n AS ∑(m-i+1)+(n+1)=7(m+1) 4 北京邮电大学自动化学院
北京邮电大学自动化学院 7 ⚫ 顺序查找的缺点是平均查找长度较大，特别是当n很大 时，查找效率低。然而，它有很大的优点是：算法简单且 适应面广。 n Pi 2 1 = ( 1) 4 3 ( 1) 2 1 ( 1) 2 1 1 ' = − + + + = + = n i n n n ASL n i S S ⚫ 当查找不成功时的情形不忽视时，查找算法的平均查找长 度应是查找成功时的平均查找长度与查找不成功时的平均 查找长度之和。 ⚫ 对于顺序查找，不论给定值key为何值，查找不成功时和 给定值进行比较的关键字个数均为n+1。假设查找成功与 不成功的可能性相同，对每个记录的查找概率也相等， 则 ，此时顺序查找的平均查找长度为： 一、顺序表的查找（顺序查找）
有序表的查找(折半查找) 、折半查我折半查找的查找过程是:先确定待查记录 所在的范围(区间),然后逐步缩小范围直到找到或找不到 该记录为止。每次将待查记录所在区间缩小一半。 ●算法实现:假设表长为n,loW、high和mid分别指向待查 元素所在区间的上界、下界和中点k为给定值,初始时,令 low=1, high=n, mid=L(low+high)/2] 让k与mid指向的记录比较 若k=rmid]key,查找成功 ·若k< r[mid]. key,则high=mid-1 若k>rmid]key,则 lowEmid+1 重复上述操作,直至 owPhigh时,查找失败 北京邮电大学自动化学院
北京邮电大学自动化学院 8 ⚫ 1、折半查找 折半查找的查找过程是：先确定待查记录 所在的范围（区间），然后逐步缩小范围直到找到或找不到 该记录为止。每次将待查记录所在区间缩小一半。 二、有序表的查找（折半查找） ⚫ 算法实现：假设表长为n，low、high和mid分别指向待查 元素所在区间的上界、下界和中点,k为给定值，初始时，令 low=1,high=n,mid=(low+high)/2 ⚫ 让k与mid指向的记录比较 ⚫ 若k==r[mid].key，查找成功 ⚫ 若k<r[mid].key，则high=mid-1 ⚫ 若k>r[mid].key，则low=mid+1 ⚫ 重复上述操作，直至low>high时，查找失败
1、折半查找 例如:已知如下11个数据元素的有序表(05,13,19, 21,37,56,64,75,80,88,92),现要查找关键 字为21和70的数据元素。 找21 1234567891011 例 51319213756647580889 low mI high 1234 67891011 513192137566475808892 d high 345678 0 1011 513192137566475808892 Ch7 2.c lowmid high Ch 2 txt 北京邮电大学自动化学院
北京邮电大学自动化学院 9 low mid high 例 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找21 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 Ch7_2.c lowmid high 例如：已知如下11个数据元素的有序表（05，13，19， 21，37，56，64，75，80，88，92），现要查找关键 字为21和70 的数据元素。 1、折半查找
34567891011 例 找70 513192137566475808892 low mid high 12345678910 513192137566475808892 low mid 13191213756 7891011 6475808892 low mid high 1234 67891011 513192137566475808892 low high mid 2345678910 513192137566475808892 北京邮电大学白他胜dow 10
北京邮电大学自动化学院 10 例 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 找70 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low high mid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 low mid high 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 high low