已知有序表为(12,18,24,35,47,50,62,83,90,115,134),当用折半查找90时,需进行多少次查找了确定成功;当查找47时,需要经过多少次确定查找成功;查找100时,需要经过多少次确定查找不成功。(写出具体比较过程)
时间: 2023-06-03 18:08:03 浏览: 455
这个问题属于数学问题,可以回答。
当用折半查找90时,需要进行4次查找才能确定成功。比较过程如下:
首先将查找范围定位在整个有序表中,即左边界为0,右边界为10。取中间位置mid = (0+10)/2=5,比较a[5] = 50与要查找的数90的大小关系,发现90比50要大,于是查找范围缩小到右半部分,左边界变为mid+1=6。再次取中间位置mid = (6+10)/2=8,比较a[8] = 90与要查找的数90的大小关系,发现相等,查找成功。
当查找47时,需要经过3次确定查找成功。比较过程如下:
先将查找范围定位在整个有序表中,即左边界为0,右边界为10。取中间位置mid = (0+10)/2=5,比较a[5] = 50与要查找的数47的大小关系,发现要查找的数小于a[5],于是查找范围缩小到左半部分,右边界变为mid-1=4。再次取中间位置mid = (0+4)/2=2,比较a[2] = 24与要查找的数47的大小关系,发现要查找的数大于a[2],于是查找范围缩小到右半部分,左边界变为mid+1=3。再次取中间位置mid = (3+4)/2=3,比较a[3] = 35与要查找的数47的大小关系,发现要查找的数大于a[3],于是查找范围缩小到右半部分,左边界变为mid+1=4。此时查找范围只有一个数,即a[4]=47,查找成功。
查找100时,需要经过4次确定查找不成功。比较过程如下:
先将查找范围定位在整个有序表中,即左边界为0,右边界为10。取中间位置mid = (0+10)/2=5,比较a[5] = 50与要查找的数100的大小关系,发现要查找的数大于a[5],于是查找范围缩小到右半部分,左边界变为mid+1=6。再次取中间位置mid = (6+10)/2=8,比较a[8] = 90与要查找的数100的大小关系,发现要查找的数大于a[8],于是查找范围缩小到右半部分,左边界变为mid+1=9。再次取中间位置mid = (9+10)/2=9,比较a[9] = 115与要查找的数100的大小关系,发现要查找的数小于a[9],于是查找范围缩小到左半部分,右边界变为mid-1=8。再次取中间位置mid = (6+8)/2=7,比较a[7] = 83与要查找的数100的大小关系,发现要查找的数大于a[7],于是查找范围缩小到右半部分,左边界变为mid+1=8。此时查找范围只有一个数,即a[8]=90,但此时要查找的数100仍然大于a[8],因此查找不成功。
阅读全文