Question

【数据结构】请教一道题，关于二分查找（折半查找）的平均搜索长度。

对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为(    )的值除以9。A、20    B、18 C、25    D、22答案是：C解释一下怎么来的？

Answer 1

链表中的位置　：1 2 3 4 5 6 7 8 9
搜索成功的长度：3 2 3 4 1 3 2 3 4
所以平均长度是 (3+2+3...+3+4) / 9
答案是： C

Answer 2

感谢二楼，也帮我解决了一个大问题！二楼说得很清楚，选ta吧！