2 qq 32793197 qq_32793197 于 2016.09.26 07:59 提问

求大神帮忙看下这个怎么做

设n个不同的整数排好序后存于T[0:n-1]中。若存在一个下标i,0<=i<n,使得T[i]=i,设计一个有效算法找到这个下标。要求算法在最坏情况下的计算时间为O(logn)。

第一行n,表示元素个数,n<=1000
第二行,n个排好序的整数

输出有两行:
第一行输出使T[i]=i的i值,如果没有找到,输出-1;
第二行输出比较次数。

2个回答

qq_29594393
qq_29594393   Ds   Rxr 2016.09.26 08:39

2分法查找,由于已经排序好,而且只有一个值为T[i]=i 最差结果,花费时间正好是 O(logn)
输出用一个计数器嘛 ,查找一次加一,最后输出就得

caozhy
caozhy   Ds   Rxr 2016.09.27 01:08
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
《SQL入门经典》学习笔记
第一部分  SQL概念综述 第1章  欢迎来到SQL世界 1.4.1 表命名标准 表的名称以_TBL作为后缀,表的索引以_INX为后缀 1.4.3 表的构成 字段是表里的一列,记录是表里的一行 第二部分  建立数据库 第2章  定义数据结构 2.2.1 定长字符串 CHARACTER(n): n为最大字符数,通常用空格来填充数量不足的字符 2.2.2 变长字符串
office解码
我不会用 我下载的时候只有这个 又不能解码 所以 求大神帮忙
anroid xmpp即时通讯的问题 求大神帮忙看下
本人刚学android不久,现在再做一个xmpp的demo 客户端发送消息时 chat.sendMessage();可以填两种参数 一种是直接发送字符串,一种是发送一个Message 对象  收到消息的监听类如下 public class TaxiChatManagerListener implements ChatManagerListener { private Context mCon
一个需要了解的DLL文件
求帮忙看下,这个DLL文件看不懂,为什么总是需要很长的描述呢
应用程序正常初始化0xc0000142,请单击确定关闭程序
这个问题大多是杀毒残留,但也有可能是你卸载某个软件不正确留下的注册表残留。杀毒后,病毒被删除,但启动项里相关加载设置还在,解决方法就是以下方法,如果找不到那个加载失败的启动项就可能是做了伪装,具体伪装到哪个启动项需要分析系统环境。启动项并不一定指向特定的dll名字,提示中的加载失败的项也可能只是启动项其中一个需要调用的文件,而这个文件可能被相关软件程序卸载的时候一并删除了,所以要了解你所有启动项的
新浪漫步者6.1
感觉很不好的一个软件 求更好的 有没有大神帮忙!
fifo to uart
VHDL 带fifo的uart 源代码,求大神帮忙修改。
VS2010编写的服务
求高手帮忙看下,断线报警器启动不了是怎么回事
国际标准智商测试题 (转载)
​国际标准智商测试题 (转载)     智商,就是IQ(Intelligence Quotient的简称),通俗地可以理解为智力,是指数字、空间、逻辑、词汇、创造、记 忆等能力,它是德国心理学家施特恩在1912年提出的。智商表示人的聪明程度:智商 越高,则表示越聪明。想检验自己的智商是多少吗?这并不困难,以下就是一例国内 较权威的IQ测试题,请在30分钟内完成(30题),之后你就
这个课程设计怎么弄,求大神帮忙!!!
这个课