Fixed Point

Given an array of N distinct integers sorted in ascending order, write a function that returns a Fixed Point in the array, if there is any Fixed Point present in array, else returns -1. Fixed Point in an array is an index i such that arr[i] is equal to i. Note that integers in array can be negative.

Examples :

Input: arr[] = {-10, -5, 0, 3, 7}
Output: 3 // arr[3] == 3

Input: arr[] = {0, 2, 5, 8, 17}
Output: 0 // arr[0] == 0

Input: arr[] = {-10, -5, 3, 4, 7, 9}
Output: -1 // No Fixed Point

Solution

Use binary search to find out such an element where array[i] == i.

Suppose we are at index i , then there are three possibilities:

• A[i] < i , this implies that all the numbers at index less than i cannot be fixed, so we need to check in the interval (i+1, N)
• A[i] > i this implies that all the numbers at index greater than i cannot be fixed, so we need to check in the interval (0, i - 1) 
• A[i] == i this implies that the number is fixed , so output it.

Code
int fixed_point(int array[], int begin, int end){

if(begin > end)

return -1;

int mid = (begin + end)/2;

if(array[mid] > mid)

return fixed_point(array, begin, mid-1);

else if(array[mid]<mid)

return fixed_point(array, mid+1, end);

else

return mid;

}

Complexity

• Time : O(log N)
• Space : O(1)