对于一个给定的有序序列[2, 5, 8, 12, 16, 23],使用折半查找(二分查找)查找数值16,需要比较多少次?
答案解析
核心考点说明:本题考察折半查找(二分查找)的过程。
解题思路分析:折半查找每次将查找区间缩小一半。第一次比较是和中间元素比较,根据大小调整查找区间。直到找到目标元素或区间为空。
选项分析:
- A:错误。第一次比较中间元素12,发现16>12,查找区间变成[16, 23],第二次比较中间元素16,找到了,所以一共比较2次。
- B:正确。第一次比较中间元素12,16>12,区间变为[16,23],第二次比较中间元素16,正好命中,一共比较2次。
- C:错误。此比较次数与二分查找过程不符。
- D:错误。此比较次数与二分查找过程不符。
易错点提醒:折半查找每次查找区间缩小一半,理解查找过程是关键。
正确答案:A