查看: 183|回复: 0
收起左侧

关于数据结构二分法查找成功和失败的平均查找长度

[复制链接]
发表于 2020-4-24 09:38:13 | 显示全部楼层 |阅读模式 简体中文繁體中文
题目:已知一个有序表为(13 18 24 35 47 50 62 83 90 155 134)当用二分法查找算法进行元素搜索时,成功的平均查找长度和失败的平均查找长度各为多少


做这种题目的时候,应该画出二叉树。然后把叶子补足。叶子的高度zhidao就是查找失败的次数。然后求和除以叶子数目就是失败的平均查找长度。而非叶子节点就是成功的回,高度就是成功的查找次数,然后除以非叶子节点的数目,就是成功的平均长度。
对于答11个节点,其构成的二叉树成功的查找长度是
(1x1+2X2+3x4+4x4)/11=33/11
失败的查找长度是

(4x8+3x4)/(8+4)=44/12


举个例子吧。假定数组中的成为二分查找数的内节点,然后补上叶子节点代表查找失败的。  比如只有一个节点a。那么成功的查找会是 1X1/1=1 ,一次比较,高度为1,处以内节点数目。失败的查找应该是不等于1的,还需要两次查找,分别是左右叶子节点,1X2/2=1。
如果是两个节点,假设a和b,并且不失一般性,设b为a的左节点,那么b的两个叶子节点代表失败情况,需要2次查找,a还有一个右节点代表失败情况,需要一次查找,(2X2+1X1)/3=5/3

依次类推就可以了。




UNP7X]JGG@@41X{EUB18X8L.jpg
KN(O]~AJ2VCUBL2}SD8(W~B.jpg
您需要登录后才可以回帖 登录 | 注册会员

本版积分规则