首页 > 试题广场 >

有一个有序表为{1,3,9,12,32,41,45,62,7

[单选题]
有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当折半查找值为82的结点时,____次比较后查找成功。
  • 1
  • 4
  • 2
  • 8
{1,3,9,12,32,41,45,62,75,77,82,95,100} 一共13个数,折半取中间第7个数,注:(1+13)/2=7。第一次比较即82与第7个数45比较。45<82,取45右边的第一个数至最后一个数的数列进行折半。此时折半取第10个数,注:(8+13)/2=10。第二次比较即82与第10个数77比较。77<82,取77右边第一个数至最后一个数的数列进行折半。此时折半取第12个数,注:(11+13)/2=12。第三次比较即82与第12个数95比较。95>82,取95左边第一个数至77右边第一个数即82进行折半,此时82=82。折半完毕。
编辑于 2019-12-11 20:08:09 回复(0)
偶数个数时,向下取,所以第二次比较的是77,而不是82。
发表于 2018-04-26 21:54:44 回复(0)
B
4次,分别和45、77、95、82进行比较
首先和中间值45比较,82比45***择右边,右边六个数和中间值77比较,82比77***择右边,右边3个数选择中间值95进行比较,82比95小选择左边,左边1个数和82比较相等
发表于 2017-01-27 09:31:13 回复(0)
一共13个数 下标为0-12   
第一次查找 用left+right即(0+12)/2=6  找到下标为6的数45 因为目标数82>45  所以left+1 
第二次查找 left变为6+1=7 left+right(7+12)/2=9 找到下标为9的数 77  因为目标数82>77 所以left+1
第三次查找 left变为9+1=10 left+right(10+12)/2=11 找到下标为11的数95 因为目标数82<95 所以left-1
第四次查找 left变为(11-1)=10 而right变为95的下标数11 left+right为(10+11)/2=10 找到下标为10的数82  与目标数相等  所以查询四次
发表于 2020-12-11 15:53:52 回复(0)

第一次与45比较,大于45则在右半部分查找,第二次与77比较,大于77继续在右边查找,第三次与95比较,小于95则在左边查找,第四次与82比较相等查找成功。

发表于 2020-03-08 10:55:36 回复(0)
首先和中间值45比,82比45***择右边,右边六个数(偶数个数时向下取所以选择77)和中间值77比较,82比77***择右边。
发表于 2019-11-14 21:14:38 回复(0)
两次折半加两次查找
发表于 2019-05-10 13:19:50 回复(0)