工学
单选题对具有n个元素的有序表采用二分查找法，则算法的时间复杂性为（）A O（n）B O（n2）C O（1）D O（log2n）
题目
O（n）
O（n2）
O（1）
O（log2n）
相似问题和答案
第1题：
对具有n个元素的有序表采用二分查找，则算法的时间复杂性为______。
A．O(n)
B． O(n2)
C． O(1)
D． O(log2n)
解析： 参见有序表采用二分查找时，算法的时间复杂性定义。二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大，但允许相邻元素值相等) 。当有序线性表为顺序存储时才能采用二分法查找，并且二分法查找的效率要比顺序查找高得多。
第2题：
设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过()。
A.log2+1
B.log2(n-1)
C.log2n
D.log2(n+1)
第3题：
使用二分查找算法在一个有序序列中查找一个元素的时间复杂度为()
A.O(N)
B.O(logN)
C.O(N*N)
D.O(N*logN)
第4题：
性表中采用折半查找法(二分查找法)查找一个数据元素，线性表应(54)。
A．数据元素按值有序
B．采用顺序存储结构
C．据元素按值有序，并且采用顺序存储结构
D．据元素按值有序，并且采用链式存储结构
解析：只有当线性表中数据元素按值大小有序排列，并且采用顺序存储结构时才能使用折半查找方法查找元素。即使线性表中数据元素按值大小有序排列，但采用的不是顺序存储结构(如链式)，仍然不能够采用折半查找方法。本题应选C。
第5题：
对于长度为n的线性表，若进行顺序查找，时间复杂性为【 】；若进行二分查找，则时间复杂性为【 】。
O(n),O(10g2n)
第6题：
● 对 n 个元素的有序表 A[1..n]进行二分（折半）查找，则成功查找到表中的任意一个元素时，最多与A 中的 （39） 个元素进行比较。
（39）
第7题：
顺序查找一个具有n个元素的线性表，二分查找一个具有n个元素的有序表，其时间复杂性为______。
A．O(n)
B．O(log2n)
C．O(n2)
D．O(nlog2n)
第8题：
对n个元素的有序表A[1．．n]进行二分(折半)查找(除2取商时向下取整)，查找元素A[i](1≤i≤n)时，最多与A中的(57)个元素进行比较。
A．n
B．[log2n]-1
C．n／2
D．[log2n]+1
解析：折半查找不成功时候需要比较次数最多，且最多不超过[log2n]+1次。
第9题：
二分查找一个具有n个元素的有序表，其时间复杂度为______。
A．O(n)
B．O(n2)
C．O(log2n)
D．(nlog2n)
解析：二分法中查找时间t与查找次数m呈比例关系，2m=n(n为极限查找个数)，m=log2n，所以查找时间复杂度与log2n相关。
第10题：
