N个元素的有序数组A，判断是否有 A[i]=i 存在

可能原帖默认是整数数组，否则题目就没定义好，起始点不等的区间一般总有足够多的浮点数使得A[i]!=i，即元素之间找不到限制关系，复杂度不会*低于O(n).(*可能会有结合具体数据的启发性算法快于O(n)) － , 11个月前
		@jge: 即便规定是整数数组也没有关系的，不影响分析的结果 － , 11个月前
		@半瓶墨水：未必吧，假如题设是严格有序的整数数组，为了循环算法，题目变为在索引范围[a,b]上寻找A[i]=i(a<=i<=b)。令k=floor((a+b)/2)考虑A[k]-k，若为0则k就是答案；若为负，注意严格有序使得A[k]-A[i]>=k-i (a<=i － , 11个月前
		@jge: 不错，严格有序的整型数组确实会影响分析的结果。因为严格有序的整数数组其任意两点之间的斜率大于等于45度，我的推理就不成立了。 － , 11个月前