在等概率情形,P1=1m,i=1,2,…,n 在查找不成功情形, ASL=n+1
. ( ) ( ) = + = + = − + = n i succ n n n n n i n ASL 1 2 1 2 1 1 1 1 在等概率情形，pi = 1/n, i = 1, 2, , n。 在查找不成功情形，ASLunsucc = n+1
有序顺序表的顺序查找 (10,20 30,40,50,60) 20 30 50 60
◼ 有序顺序表的顺序查找 ( 10, 20, 30, 40, 50, 60 ) 10 50 60 = = = = = = 20 30 40 < < < < < < > > > > > > ( ) 2 7 1 6 1 5 0 = + = i= succ ASL i ( ) 7 27 1 6 7 1 5 0 = = + + = i= unsucc i ASL
基于有序顺序表的折半查找 n说n个对象存放在一个按其关键码从小到大排 好了序的有序顺序表中 折半查找时,先求位于查找区间正中的对象 的下标mid,用其关键码与给定值x比较: ◆A.data[mid].key==x,查找成功; A.data[mid].key>x,把查找区间 缩小到表的前半部分,继续折半查找 A.data[mid].key<x,把查找区间 缩小到表的后半部分,继续折半查找。 如果查找区间已缩小到一个对象,仍未找到 想要查找的对象,则查找失败
基于有序顺序表的折半查找 ◼ 设n个对象存放在一个按其关键码从小到大排 好了序的有序顺序表中。 ◼ 折半查找时, 先求位于查找区间正中的对象 的下标mid，用其关键码与给定值x比较: ◆ A.data[mid].key == x, 查找成功； ◆ A.data[mid].key > x, 把查找区间 缩小到 表的前半部分，继续折半查找； ◆ A.data[mid].key < x，把查找区间 缩小到表的后半部分，继续折半查找。 ◼ 如果查找区间已缩小到一个对象，仍未找到 想要查找的对象，则查找失败
012345678 610134681012 查找ow mid high 5678 681012 low mid high 5 6 low mid high 查找成功的例子
查找成功的例子 6 -1 0 1 3 4 6 8 10 12 0 1 2 3 4 5 6 7 8 查找 low mid 6 high 6 8 10 12 5 6 7 8 low mid high 6 6 5 low mid high 6
012345678 51[10134681012 查找ow mid high 5678 681012 low mid high 5 56 low mid high 查找失败的例子
查找失败的例子 5 -1 0 1 3 4 6 8 10 12 0 1 2 3 4 5 6 7 8 查找 low mid 5 high 6 8 10 12 5 6 7 8 low mid high 5 6 5 low mid high 5