数据结构请教一道题,关于二分查找（折半查找）的平均搜索长度.对于长度为9的有序顺序表,若采用折半搜索,在等概率情况下搜索成功的平均搜索长度为()的值除以9.A、20B、18C、25D、22

Question

【数据结构】请教一道题,关于二分查找（折半查找）的平均搜索长度.
对于长度为9的有序顺序表,若采用折半搜索,在等概率情况下搜索成功的平均搜索长度为( )的值除以9.
A、20 B、18 C、25 D、22答案是：

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祝你学习愉快,考研顺利!加油!