C为找到表中其关键字与给定值相等的第个记录时,和给 定值已进行过比较的关键字个数 对于顺序查找算法,等概时查找成功的平均查找长度 H: AcN=>pc=I>i=In(n+D=n+I 则顺序查找算法查找成功时的时间复杂度为on) 在实际应用的大多数情况下,查找成功的可能性比不 成功的可能性大的多,特别是当n很大时,查找不成功的概 率可忽略不计.但当查找不成功的概率不能忽略时,查找 算法的平均查找长度应当是查找成功时的平均查找长度和 查找不成功时的平均查找长度之和 对于顺序査找,不论给定关键字值为何值,查找不成功 时和给定值进行比较的关键字个数均为n+1.设查找成功和 不成功的概率相等,即均为二分之一,对每个记录的查找 概率也相等
为找到表中其关键字与给定值相等的第i个记录时, 和给 定值已进行过比较的关键字个数. 对于顺序查找算法, 等概时查找成功的平均查找长度 i c 为: 2 1 2 1 1 ( 1) 1 1 + = + = = = = = n n n n i n ACN p c n i n i i i 则顺序查找算法查找成功时的时间复杂度为O(n). 在实际应用的大多数情况下, 查找成功的可能性比不 成功的可能性大的多, 特别是当n很大时, 查找不成功的概 率可忽略不计. 但当查找不成功的概率不能忽略时, 查找 算法的平均查找长度应当是查找成功时的平均查找长度和 查找不成功时的平均查找长度之和. 对于顺序查找, 不论给定关键字值为何值,查找不成功 时和给定值进行比较的关键字个数均为n+1. 设查找成功和 不成功的概率相等, 即均为二分之一, 对每个记录的查找 概率也相等
则P1=1/2n,此时顺序查找的平均查找长度为: n+11 ACN=∑pC1+ n+1n+1,n+13(n+1) 22n7 2 4 4 顺序査找的优点:算法简单,适应面广,查找表中的记 录按关键字值的排列即可无序,也可有序,查找表的存储结 构即可为顺序,也可为链表 顺序查找的缺点:平均查找长度较大,尤其当n较大时 查找效率较低 712折半查找 折半查找也叫二分査找,其前提条件是:查找表必须以 顺序表的结构存储,且查找表中的记录必须按关键字值有序 排列 以后所举例子中假设查找表中的记录按关键字值递增有 序排列 下面用具体的例子说明折半查找的基本思想和手工操作 的过程
则 p n ,此时顺序查找的平均查找长度为: i =1/ 2 4 3( 1) 2 1 4 1 2 1 2 1 2 1 1 1 + = + + + = + = + + = + = = n n n n i n n ACN p c n i n i i i 顺序查找的优点: 算法简单, 适应面广, 查找表中的记 录按关键字值的排列即可无序, 也可有序, 查找表的存储结 构即可为顺序, 也可为链表. 顺序查找的缺点: 平均查找长度较大, 尤其当n较大时 查找效率较低. 7.1.2 折半查找 折半查找也叫二分查找, 其前提条件是: 查找表必须以 顺序表的结构存储, 且查找表中的记录必须按关键字值有序 排列. 以后所举例子中假设查找表中的记录按关键字值递增有 序排列. 下面用具体的例子说明折半查找的基本思想和手工操作 的过程
例:设在顺序存储的有序表中各记录的关键字为: 234567891011 03四9237566475808892 现要求查找关键字值为21的记录 查找过程如下:设三个变量分别为l,hg,mid,它们的初值 0=1hg=1lmd=(o+hig)/2」=6,则它们的初始指向如 1234567891011下左图.第一次比较: 03921375664758088927 mid].key=7ey=56k=21 hig=mid-1=6-1=5 hig mid =L(low +hig)/2]=3 low mid hig第二次比较: [mid].key=13key=19<k=21 p=md+1=3+1=4,md=(o+hg)/2」=4 mnhg第三次比较:1mlky=n1ky=21-=k=21 Ow 所以查找成功
例: 设在顺序存储的有序表中各记录的关键字为: 现要求查找关键字值为21的记录. 查找过程如下: 设三个变量分别为 1 2 3 4 5 6 7 8 9 10 11 05 13 19 21 37 56 64 75 80 88 92 low,hig,mid , 它们的初值 low =1,hig =11,mid = (low + hig)/ 2 = 6 , 则它们的初始指向如 1 2 3 4 5 6 7 8 9 10 11 下左图. 05 13 19 21 37 56 64 75 80 88 92 low mid hig 第一次比较: ( )/ 2 3 1 6 1 5 [ ]. [6]. 56 21 = + = = − = − = = = = mid low hig hig mid r mid key r key k low mid hig 第二次比较: r[mid].key = r[3].key =19 k = 21 low = mid +1= 3 +1= 4,mid = (low + hig)/ 2 = 4 low mid hig 第三次比较: r[mid].key = r[4].key = 21= k = 21 所以查找成功
若现需查找关键字值为85的记录,则过程如下:第一次比较: 1234567891011 [mid.key=r[6key=56<k=85 051319211375664758088 ∴l0w=mid+1=6+1=7 (+hig)/2」=9 hig 第二次比较 lo id hig:rlmid .keyrlg).key=80 <k=85 ∴lOn=mid+1=9+1=10 mid hig mid=(o+hig)/2」=10.5」=10 第三次比较: low . r[mid].key=r[10].key=88>k=85 hig=mid-1=10-1=9 O hig g <l=10 查找不成功.其它例子可见教材P.173~P174.算法的C函数 可见教材P175 下面分析折半查找的平均查找长度
若现需查找关键字值为85的记录, 则过程如下: 第一次比较: 1 2 3 4 5 6 7 8 9 10 11 05 13 19 21 37 56 64 75 80 88 92 low mid hig ( )/ 2 9 1 6 1 7 [ ]. [6]. 56 85 = + = = + = + = = = = mid low hig low mid r mid key r key k low mid hig 第二次比较: ( )/ 2 10.5 10 1 9 1 10 [ ]. [9]. 80 85 = + = = = + = + = = = = mid low hig low mid r mid key r key k 第三次比较: low mid hig 1 10 1 9 [ ]. [10]. 88 85 = − = − = = = = hig mid r mid key r key k low hig hig = 9 low =10 查找不成功. 其它例子可见教材P.173~P.174. 算法的C函数 可见教材P.175 下面分析折半查找的平均查找长度