Searching and Sorting: Get the fixed point in an array

Problem Statement:

You are given an sorted ascending array, you need to find the fixed point.

A fixed point is an element in the array, such that index i and arr[i] are same.

Example

Input: {-7, -4, 0, 3, 6}
Output: 3
Because arr[3] == 3

Solution

There are multiple ways to solve this problem:
1. Linear Search
2. Binary search

1. Linear Search:

Here we check for every element of arr[i] with i and then return that element

Time Complexity: O(n)

2. Binary Search:

As the array is sorted, we can use binary search.

In binary search, we check if the middle element is a fixed point or not.

else, if the index of the middle element is greater than value at the index, then move towards right.

else, move towards left.

Time Complexity: O(logn)

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <sstream> 

using namespace std;

int linear_earch(int arr[], int n)  
{  
    int i;  
    for(i = 0; i < n; i++)  
    {  
        if(arr[i] == i)  
            return i;  
    }  
      return -1;  
} 

int binary_search(int arr[], int low, int high)  
{  
    if(high >= low)  
    {  
        int mid = (low + high)/2; 
        if(mid == arr[mid])  
            return mid;  
        if(mid > arr[mid])  
            return binary_search(arr, (mid + 1), high);  
        else
            return binary_search(arr, low, (mid -1));  
    }  
  
    return -1;  
}  
  
/* Driver code */
int main()  
{  
    int arr[] = {-1, 0, 1, 3, 5, 10};  
    int n = sizeof(arr)/sizeof(arr[0]);  
    cout << "Fixed Point is using linear search " << linear_earch(arr, n)<<endl;  
    cout << "Fixed Point is using binary search " << binary_search(arr, 0, n-1)<<endl;  
    return 0;  
}  

Output:

Fixed Point is using linear search 3
Fixed Point is using binary search 3