已知一个有序表(12,24,33,43,56,65,78,81,89,92,101),当二分查找值为68的元素时,查找失败的比较次数为多少
时间: 2023-10-09 16:08:38 浏览: 51
二分查找算法的过程是不断将待查找区间缩小一半,直到找到目标元素或者区间缩小为0为止。因此,失败的比较次数就是最后一次比较的次数。
在这个有序表中,二分查找的过程如下:
1. 初始时,待查找区间为整个有序表,即[12, 24, 33, 43, 56, 65, 78, 81, 89, 92, 101]。
2. 将待查找区间的中间元素56和目标元素68进行比较,发现目标元素大于中间元素,因此目标元素应该在区间的右半部分。新的待查找区间为[65, 78, 81, 89, 92, 101]。
3. 将新的待查找区间的中间元素89和目标元素68进行比较,发现目标元素小于中间元素,因此目标元素应该在区间的左半部分。新的待查找区间为[65, 78, 81]。
4. 将新的待查找区间的中间元素78和目标元素68进行比较,发现目标元素小于中间元素,因此目标元素应该在区间的左半部分。新的待查找区间为[65]。
5. 将新的待查找区间的唯一元素65和目标元素68进行比较,发现目标元素大于中间元素,因此目标元素不在该区间内。
因此,二分查找值为68的元素时,查找失败的比较次数为4次。
阅读全文