I'm trying to write a recursive algorithm that returns true if at least one array[i] == i. And false if there is no array[i] = i.

Also, the parameters needed are (int * arr, int start, int end). So i'll be traversing the array with a pointer. For example:

```
int A[] = {-50,-10,0,1,3,5,8,10};
cout << sameIndex(A,0,7) << endl; //displays 1 (true) since A[5] == 5
```

The part I'm having a lot of trouble is making it O(log n). I can't see where dividing the array into 2 each function call is going to get the correct solution. And trying to come up with the structure of this algorithm is going over my head. Can someone point me in the right direction? I'm not looking for the answer, I just don't know how to start solving this problem recursively, much less in O(log n) time.

Forgot to mention that yes the integers are distinct AND sorted.

I figured it out! Captain Giraffe and Henrik are correct but they use slightly different methods. I chose to go with Captain Giraffe's method because it is slightly easier and more intuitive using binary search. Henrik's uses a little "trick" of finding the solution by subtracting array[i] - i to check if they equal 0. Anyways here is the solution:

```
bool sameIndex(int * A, int start, int end)
{
int mid = (start + end)/2;
if(start <= end)
{
if(*(A + mid) == mid)
return true;
else if(*(A + mid) > mid) //search left
return sameIndex(A, start, mid - 1);
else //search right
return sameIndex(A, mid + 1, end);
}
return false;
}
```

I was making it way harder than it actually was. But thanks for the help guys!