Index Same As Element

Suppose that you are given a sorted sequence of distinct integers{a1,a2,...an} . Give an O(log(n)) algorithm to determine whether there exists an index i such at ai = i . For example, in arr[]={-1,0,3,6,7} since arr[3] == 3 the solution should be three.

Solution
We do a binary search for the array. Compare the index of the curr element(ind) and the current elements(arr[ind]). If the ind is less than arr[ind] then match can be found only in the lower half(since all elements are distict). Similarly if ind is greater than arr[ind] then match can be found in the upper half. If Equal then match is found.

pseudo code

int matchIndToElem(int arr[], int size)
{
low = 0;
upper = size - 1;
mid = (low+upper)/2;
while(low < upper)
{
if( mid == arr[mid])
{
printf("Match Found at index %d",mid);
return mid;
}
else if( mid < arr[mid])
{
low = low;
upper = mid;
mid = (upper + low)/2;
}
else
{
low = mid;
upper = upper;
mid = (upper +low)/2;
}
}
if(arr[low] == low)
{
printf("Match Found at index %d",low);
return low;
}
return -1;
}