首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
在长度为n的有序线性表中进行二分查找,最坏情况下需要比较的次数是
在长度为n的有序线性表中进行二分查找,最坏情况下需要比较的次数是
admin
2009-08-25
60
问题
在长度为n的有序线性表中进行二分查找,最坏情况下需要比较的次数是
选项
A、O(n)
B、O(n2)
C、O(log2n)
D、O(nlog2n)
答案
C
解析
二分查找法也称为折半查找法。它的基本思想是:将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2],则找到x,算法终止;如果x<a[n/2],则只要在数组a的左半部继续搜索x(这里假设数组元素呈升序排列);如果x>a[n/2],则只要在数组a的右半部继续搜索x。每次余下n/(2i)个元素待比较,当最后剩下一个时,即n/(2i)=1。故n=2i;所以i=log2n。
转载请注明原文地址:https://kaotiyun.com/show/Fcnp777K
本试题收录于:
二级Java题库NCRE全国计算机二级分类
0
二级Java
NCRE全国计算机二级
相关试题推荐
设有两个数据库表,父表和子表之间是一对多的联系,为控制子表和父表的联系,可以设置“参照完整性规则”,为此要求这两个表
连续执行以下命令,最后一条命令的输出结果是SETEXACtTOFFa-’’北’’b=(a=’’北京交通’’)?b
假设职员表已在当前工作区打开,其当前记录的“姓名”字段值为“李彤”(C型字段)。在命令窗口输入并执行如下命令:姓名=姓-’’出勤’’?姓名屏幕上会显示
如果运行一个表单,下列事件首先被触发的是
为Employee表增加一个字段“出生日期”,正确的SQL语句是
为“评分”表的“分数”字段添加有效性规则:“分数必须大于等于0并且小于等于10”,正确的SQL语句是
下面程序的运行结果是:SETTALKOFFn=1DOproclWITH(n)?n+2PROCEDUREproc1PARAMETERSnFORk=2TO4n=
下列叙述中正确的是
(1)在mybase数据库中建立视图myview,视图中包括客户名、订单号、图书名、单价、数量和签订日期字段。然后使用SQLSELECT语句查询:“吴”姓读者(客户名第一个字为“吴”)订购图书情况,查询结果按顺序包括myview视图中的全部字段,并要求先按
以下描述中,不是线性表顺序存储结构特征的是()。
随机试题
Acaraccident______himfromplayingfootball.
A.限制苯丙氨酸摄入量B.口服碘化钾C.口服甲状腺片D.加强训练,无特殊治疗E.生长激素替代治疗1岁男孩,表情呆滞,刚会坐,眼距宽,眼裂小,双眼外侧角上斜,舌大外伸,通贯手,四肢肌张力低下。应采取的治疗措施是
男性骑跨伤致尿道损伤的部位是()
某企业第1年年初向银行借款100万元,第1年年末又借款100万元,第3年年初再次借款100万元,年利率均为1%,到第4年年末一次偿清,应付本利和为( )万元(按复利计算)。
建设人程项目质量的影响因素中的环境因素主要包括()。
按物质产生爆炸的原因和性质分类,通常将爆炸分为()。
下列选项中,应缴纳个人所得税的为()
即使走到成功边缘,也因为害怕失败而退缩,这属于()。
(2017年潍坊寒亭)师生在人格上是___________的关系。
(1)被捕入狱(2)成为劳模(3)痛改前非(4)刑满释放(5)入室盗窃
最新回复
(
0
)