顺序查找的平均查找长度 设查找第i个元素的概率为p,查找到第i个元素 所需比较次数为c,则查找成功的平均查找长度: ASL SucC ∑pc;:(∑P=1) i=1 在顺序查找情形,c1=ni+1,i=1,…,n,因此 ASD、w=∑p1(n-i+1) 在等概率情形,P;=1/m,i=0,1,,n-1 AsLI n(n+ + 2 2
顺序查找的平均查找长度 = = = = n i i n i ASLsucc pi ci p 1 . ( 1) 1 ( ) 1 = − +1 = ASL p i n i succ i n . ( ) ( ) = + = + = − + = n i succ n n n n i n ASL 1 2 1 2 1 1 1 1 n 设查找第 i 个元素的概率为 pi，查找到第 i 个元素 所需比较次数为 ci，则查找成功的平均查找长度: 在顺序查找情形，ci = n-i +1, i = 1, , n，因此 在等概率情形，pi = 1/n, i = 0, 1, , n-1
812有序表的查找 折半查找:先求位于查找区间正中的对象的 下标mid,用其关键字与给定值比较: n Element(mid. getKey()=x,查找成功 o Element mid getKey()>x,把查找区间缩小 到表的前半部分,再继续进行对分查找; n Element mid- getKey()<x,把查找区间缩小 到表的后半部分,再继续进行对分查找。 每比较一次,查找区间缩小一半。如果查找 区间已缩小到一个对象,仍未找到想要查找 的对象,则查找失败
8.1.2 有序表的查找 折半查找：先求位于查找区间正中的对象的 下标mid，用其关键字与给定值x比较: Element[mid].getKey( ) = x，查找成功； Element[mid].getKey( ) > x，把查找区间缩小 到表的前半部分，再继续进行对分查找； Element[mid].getKey( ) < x，把查找区间缩小 到表的后半部分，再继续进行对分查找。 每比较一次，查找区间缩小一半。如果查找 区间已缩小到一个对象，仍未找到想要查找 的对象，则查找失败
折半查找 (1) mid=L(low+high)/2 (2)比较 STelem mid). key==key 如果 STelem mid . key==key,则查找成功, 返回md值 如果 STelem mid]. key>key,则置high=mid-1 如果 STelem mid]. key<key,则置low=mid+1 (3)重复计算mid以及比较 STele mid]. key与key 当low>high时,表明查找不成功,查找结束
折半查找： （1）mid= (low+high)/2 （2）比较 ST.elem[mid].key = = key? 如果 ST.elem[mid].key = = key，则查找成功， 返回mid值 如果 ST.elem[mid].key > key，则置high=mid-1 如果 ST.elem[mid].key < key，则置low=mid+1 (3) 重复计算mid 以及比较ST.elem[mid].key与 key， 当low>high时，表明查找不成功，查找结束
面叫013146812国 查找 查找 OZO mia high mid high 681012 low mid high low mid high 查找成功 查找失败国 low mid high low mid high 查找成功的例子 查找失败的例子
查找成功的例子 查找失败的例子
算法8.2 int search bin( SSTable ST, Key Type key)/折半查找 f int low, high, mid low=l; high-STlength while (low high) f mid=(low+high)/2 if(eQ(key, ST elem [ mid]. key)) return mid else if (lt(key, STelem mid. key)) high=mid-1 else low-mid+1 eturn o
算法8.2 int Search_Bin(SSTable ST,KeyType key) //折半查找 { int low,high,mid; low = 1; high=ST.length; while (low < high) { mid = (low+high)/2; if (EQ(key,ST.elem[mid].key)) return mid; else if (LT(key,ST.elem[mid].key)) high=mid-1; else low=mid+1; } return 0; }