Value equal to index value

Given an array  N positive integers. we should find the elements whose value is equal to that of its index value.

Input: 
N = 5
Arr[] = {15, 2, 45, 12, 7}
Output: 2
Explanation: Only Arr[2] = 2 exists here.

Method 1 (Linear Search)
iterate through array elements and if  arr[i] == i. Return the first such index found. 

if we dont find than return -1

implementation:

int linearSearch(int arr[], int n)  
{  
      
    for(int i = 0; i < n; i++)  
    {  
        if(arr[i] == i)  
            return i;  
    }  
  
    /* If no fixed point present then return -1 */
    return -1;  
}  

Time Complexity: O(n)

space complexity:O(1)

Method 2 (Binary Search)
First check whether middle element is Fixed Point or not. If it is, then return it; otherwise check whether index of middle element is greater than value at the index. If index is greater, then Fixed Point(s) lies on the right side of the middle point (obviously only if there is a Fixed Point). Else the Fixed Point(s) lies on left side.

to understand binary search properly:

click on this link :

implementation:

int binarySearch(int arr[], int low, int high)  
{  
    if(high >= low)  
    {  
        int mid = (low + high)/2; /*low + (high - low)/2;*/
        if(mid == arr[mid])  
            return mid;  
        if(mid > arr[mid])  
            return binarySearch(arr, (mid + 1), high);  
        else
            return binarySearch(arr, low, (mid -1));  
    }  
  
    /* Return -1 if there is no Fixed Point */
    return -1;  
} 

Time Complexity: O(Logn)

space complexity:O(1)