回 帖 发 新 帖 刷新版面

主题:数据结构二分查找题解析?

有一个长度为12的有序表,按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为(37/12) ,查找不成功所需的平均比较次数为(49/13)
我只知道这道题的答案,但是不懂为什么?有哪位行行好的可以告诉我其中的原理?谢谢大家了!

回复列表 (共1个回复)

沙发


              /       \
             ③       ⑨
            /  \     /  \
           ①  ④   ⑦   ⑾
            \   \   \   /\
            ②  ⑤  ⑧  ⑩ ⑿
这是二分法即折半查找的mid值,

查找成功时候的平均比较次数就是:
1/12(1+2*2+3*4+4*5)

查找不成功时候的平均比较次数为:
1/13(2+3*2+4*4+5*5)

我来回复

您尚未登录,请登录后再回复。点此登录或注册