在顺序表(8,11,15,19,25,26,30,33,42,48,50)中,用二分(折半)法查找关键码值20,需做的关键码比较次数为( )。
时间: 2023-09-19 18:10:59 浏览: 204
在这个有序顺序表中查找关键码值20,可以使用二分(折半)查找算法。具体步骤如下:
1. 找到顺序表的中间位置,即$mid=(low+high)/2$,其中$low$和$high$分别为顺序表的第一个位置和最后一个位置。
2. 取中间位置的关键码值$midValue$,与待查找的关键码值进行比较。若$midValue$等于待查找关键码值,则查找成功;否则,进行下一步。
3. 若$midValue$大于待查找关键码值,则在顺序表的左半部分继续进行二分查找;否则,在顺序表的右半部分进行二分查找。
4. 重复步骤1~3,直到查找成功或左右指针交错,查找失败。
按照这个算法,在顺序表(8,11,15,19,25,26,30,33,42,48,50)中查找关键码值20,具体步骤如下:
1. 初始化$low=0$,$high=10$,$mid=5$,$midValue=26$。
2. $midValue>20$,在顺序表的左半部分($low=0$,$high=4$)继续进行二分查找。
3. $mid=2$,$midValue=15$,$midValue<20$,在顺序表的右半部分($low=3$,$high=4$)继续进行二分查找。
4. $mid=3$,$midValue=19$,$midValue<20$,在顺序表的右半部分($low=4$,$high=4$)继续进行二分查找。
5. 左右指针交错,查找失败。
可以看出,在这个过程中,共进行了3次关键码比较。因此,用二分(折半)法查找关键码值20,需做的关键码比较次数为3。
阅读全文
相关推荐













