Question

折半查找方法查找成功的平均查找长度

将关键字2，4，6，8，10，12，14，16依次存放于一维数组A[0...7]中，如果采用折半查找方法查找关键字，在等概率情况下查找成功时的平均查找长度为( )

Answer 1

判定树 如上，查找成功平均长度=1/8(1+2*2+3*4+1*5)=22/8=11/4

追问

不好意思，昨天没看到消息，答案选A ，好像不是你说的22/8

追答

没看到你的选项，你说的A，大概是21/8, 那是没把第一个算进去，所以两者差了一次。

Answer 2

山人的回答里面应该是1*4，那就对了

Answer 3

你是学的数据结构不？这个书上应该有公式的，把数带进去就可以算了

追问

(A)
21/8

(B)
7/2

(C)
4

(D)
9/2
是选A 吗？能不能告诉我公式是什么？