2013年阿里巴巴一道笔试题

Question

给定一个排好升序的数组A[1]、A[2]、.....、A[n]，其元素的值都两两不相等，请设计一高效算法找出中间所有A[i]=i的下标。

Answer 1

1，这个题目中，数组A[i]应该是个整数数组
2，由升序+两两不等可知，A[i]是个递增的数列

把A[i]连成一条线，则与直线y=x只有一个交点（或者有仅有一段重合），即满足：

如果A[i]>i，则点A[i]在直线y=x的上半部，即 对任意j>i,都有A[j]>j，i以后的区间可以抛弃；

如果A[i]<i，则点A[i]在直线y=x的下半部，即 对任意j<i,都有A[j]<j，i以前的区间可以抛弃；

这篇博客恰好是这个问题的完美解法：http://openmind.iteye.com/blog/1320859