Question

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

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

Answer 1

可以设这九个数依次为1-2-3-4-5-6-7-8-9，那么按照二分查找：第一次应该找到的是[1+9]/2=5（这就是说数字5搜索的长度为1）；第二次可以找到2个数字是[1+5]/2=3或[5+9]/2=7（3和7的搜索长度为2）；……第三次可以找到4个数字是2、4、6、8；第四次可以找到2个数字是1、9；因此将以上九个数字的搜索长度相加可以得到：1+2*2+3*4+2*4=1+4+12+8=25 即可选出答案C祝你学习愉快，考研顺利！加油！

Answer 2

链表
中的位置　：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