题目

对有序数组{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

提问时间：2020-10-04

答案

二分查找的方法要首先明白
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顺利!