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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!