折半搜索 有序顺序表 口折半搜索构造的判定树 >设满二叉树n=2h-1 则有2=n+1,h=logn+1) >平均搜索长度 ASL ICC (1*2”+2*21+3*22+…+(h-1)*2-2+h*21 n 错位相减法 (h-1)×2+1) n log2(n+1)-1slog2(n+1)-1折半搜索 ◼ 有序顺序表  折半搜索构造的判定树 ➢ 设满二叉树n=2h-1 ➢ 则有2 h=n+1，h=log2 (n+1) ➢ 平均搜索长度 9 50 = = = = = = 30 < < < < < < > > > > > > 20 40 60 10 log ( 1) 1 log ( 1) 1 1 (( 1) 2 1) 1 (1 * 2 2 * 2 3 * 2 ( 1) * 2 * 2 ) 1 2 2 0 1 2 2 1 + −  + − + = = −  + = + + + + − + − n n n n h n h h n ASL h h h￾succ  错位相减法