对200个元素的有序表二分查找次数
时间: 2023-06-18 18:07:22 浏览: 66
对于一个有序表,采用二分查找的平均查找次数为 log2(n)+1,其中n为有序表的元素个数。
因此,对于有200个元素的有序表,采用二分查找的平均查找次数为 log2(200)+1约等于8.64次。具体计算方法为:
log2(200) ≈ 7.64(取整数部分为7)
log2(200)+1 ≈ 8.64
因此,对于有200个元素的有序表,采用二分查找的平均查找次数为约8.64次。
相关问题
有序顺序表二分查找发的时间复杂度
有序顺序表二分查找的时间复杂度为 O(log n),其中 n 表示元素个数。二分查找的基本思想是将查找区间不断地缩小为原来的一半,因此时间复杂度为对数级别。具体实现时,每次比较的次数最多为 log2(n)+1 次,所以时间复杂度为 O(log n)。因此,当元素个数很大时,二分查找的效率比顺序查找要高很多。
已知一个有序表(12,24,33,43,56,65,78,81,89,92,101),当二分查找值为68的元素时,查找失败的比较次数为多少
二分查找算法的过程是不断将待查找区间缩小一半,直到找到目标元素或者区间缩小为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次。