参考答案

解析：首先分析一下这个数组，假设其中某个位置的A[i] = i，那么可以肯定的值，之前的A[x] > x，之后的A[x] < x。还有一个显而易见的性质就是中间的A[i]=i一定是连续存在的，不可能跨区域存在，因为这个数组是升序的。

我给出的方法是二分查找，具体的做法是：我们假设一个新数组B，其元素是A[i] - i的值，这样的话，B[i] = 0的时候A[i] = i，而且把B数组划分成了三个部分，左边的小于零的区域，中间的等于零的区域，右边的大于零的区域。

我第一次的想法是：二分搜索这个想象中的新数组，找到值为零的下标，但是这个下标不一定是最左边的满足条件的下标，所以我们还需要写一个while来往左移动这个下标，直到找到最左边的符合条件的下标，如下代码（假设已经通过二分查找找到了符合条件的一个下标idx）：

while(A[idx-1] == (idx-1))
     idx--;  

这样的话其时间复杂度就是O(logn) + O(n)，还是属于On)的范畴。

后来我想到，为什么只去随机命中一个目标下标呢！如果二分查找这个数据的边界的话，就能直接得到最左边符合条件的下标了！其实二分查找不仅仅适用于对一个元素的搜索，也可以用于两个、三个特定相对位置元素的搜索。每次查找的时候，假设当前位置是mid，那么只要判断当前A[mid] - mid是否小于零，以及后一个元素A[mid+1] - (mid+1) == 0就行了。

#include  <iostream>  
using namespace std;  
  
int BinarySearch(int cc[], int len)  
{  
   int l = 0, r = len, mid;  
   while (l <= r)  
   {  
      mid = l + ((r-l) >> 1);  
      if(mid == 0 && cc[mid] == mid)   // 若数组一开始就符合条件  
         return 0;  
      // 若满足条件的下标不是从0开始，则边界是前一个<0，且后一个=0  
      if (cc[mid]-mid < 0 && cc[mid+1]-(mid+1) == 0)  
         return mid+1;  
      // 二分查找边界：前一个<0，且后一个=0  
      if (cc[mid] - mid >= 0)  
         r = mid-1;  
      else  
         l = mid+1;  
   }  
   return -1;  
}  
  
int main()  
{  
   // int cc[] = {0, 1};  
   // int cc[] = {0, 1, 2, 3, 4, 5, 6, 7};  
   // int cc[] = {-9, -8, -4, -2, 4, 5, 9};  
   // int cc[] = {-5, -4, -3, 5, 6, 7};  
   int len = sizeof(cc)/sizeof(int);  
   int idx = BinarySearch(cc, len);  
   if(idx != -1)  
   {  
      while(cc[idx] == idx)  
      {  
         printf("%d ", idx);  
         idx++;  
      }  
   }  
   else  
   {  
      printf("Not found\n");  
   }  
  
   getchar();  
   return 0;  
}  

OK! 由于程序是原生的二分查找，所以时间复杂度为O(logn)，没有占用额外的空间。并且不需要区分正整数还是负整数，数据类型也可以改成double没问题。