作业帮 > 数学 > 作业

对有序数组{5,13,19,21,37,56,64,75,88,92,100}进行二分查找,等概率情况下,查找成功的平均

来源:学生作业帮 编辑:大师作文网作业帮 分类:数学作业 时间:2024/11/06 11:38:32
对有序数组{5,13,19,21,37,56,64,75,88,92,100}进行二分查找,等概率情况下,查找成功的平均查找长度(平均比较次数)是().
A.35/11 B.34/11 C.33/11 D.32/11 E.34/10
noip
对有序数组{5,13,19,21,37,56,64,75,88,92,100}进行二分查找,等概率情况下,查找成功的平均
二分查找的方法要首先明白
56 需要查找1次
19、88 需要查找2次
5和13、21和37、64和75、92和100四组中,每组两个数中一个查找3次 一个查找4次,具体谁3谁4这要看具体实现的时候的等于符号怎么划分.
每个的概率相等,为1/11
所以,平均长度=1/11×(1+2×2+3×4+4×4)=33/11 答案C正确.
祝NOIP2009顺利!