2. 计算机
  3. 设有序线性表的长度为n，则在有序线性表中进行二分查找，最坏情况下的比较次数为( )。

设有序线性表的长度为n，则在有序线性表中进行二分查找，最坏情况下的比较次数为( )。

admin2022-09-09  37
问题 设有序线性表的长度为n，则在有序线性表中进行二分查找，最坏情况下的比较次数为(          )。
选项 A、n(n-1)／2
B、n
C、nlog2n
D、log2n
答案D
解析 有序线性表的长度为n，设被查找元素为z，则二分查找的方法如下：将x与线性表的中间项比较，中间项的值等于x，则说明已查到，查找结束；若x小于中间项的值，则在线性表的前半部分(中间项以前的部分)以相同的方法进行查找；若x大于中间项的值，则在线性表的后半部分(中间项以后的部分)以相同的方法进行查找。这个过程一直进行到查找成功或子表长度为0(说明线性表中没有这个元素)为止。对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次。本题选择D选项。
转载请注明原文地址:https://kaotiyun.com/show/0K6p777K
本试题收录于： 二级Python题库NCRE全国计算机二级分类
0

二级Python

NCRE全国计算机二级

相关试题推荐
随机试题
最新回复(0)