设一组初始记录关键字序列为(13,18,24,35,47,50,62,83,90,115,134),则利用二分査找算法查找关键字90需要比较的关键字个数为()
A、
1
B、
2
C、
3
D、
4
【正确答案】:B
【题目解析】:
二分查找(Binary Search)的查找过程为每次用给定值与处在表的中间位置的数据元素的键值进行比较,确定给定值的所在区间,然后逐步缩小查找区间。重复以上过程直至找到或确认找不到该数据元素为止。
首先,取区间中间位置mid=(1+11)/2=6,即取中间位置6上的元素50,与90比较。
因为50<90,说明若90存在,必在[62,134]中。故新的mid=(7+11)/2=9,即取中间位置9上的元素90,与90比较。
因为90=90,比较结果表明正是待查元素,查找成功。
故比较的次数为2次。