# Find a Fixed Point in a Given Array  Difficulty Level Easy
Frequently asked in Amazon Factset Hike Uber
Array Binary Search Divide and Conquer

## Problem Statement  Given an array of n distinct elements, find a fixed point in a given array, where a fixed point means the element value is the same as the index.

## Example  Input

5

arr[] = {0,4,8,2,9}

Output

0 is a fixed point in this array because value and index both are the same which is 0.

Input

6

arr[] = {2,7,9,3,10,8}

Output

3 is a fixed point in this array because value is 3 and index is 3.

## Approach 1(Linear Search)  Here we traverse from start to end of the array and check the condition for the fixed point and if the condition is true then print the element and else print “`No fixed point in the array`“.

### Algorithm

1. Till the end of the array, for each element
2. check if the element value is the same as the index value, If true print the element.

### Implementation

#### C++ Program for Find a Fixed Point in a Given Array

```#include <bits/stdc++.h>
using namespace std;
int main()
{
int N;
cin>>N;
int arr[N];
for(int i=0;i<N;i++)
{
cin>>arr[i];
}
for(int i = 0; i < N; i++)
{
if(arr[i] == i)
{
cout<<arr[i]<<endl;
return 0;
}
}
cout<<"No fixed point in the array \n";
return 0;
}```

#### Java Program for Find a Fixed Point in a Given Array

```import java.util.Scanner;
class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
int temp=0;
for(int i=0;i<n;i++)
{
if(a[i] == i)
{
System.out.println(a[i]);
temp=1;
i=n;
}
}
if(temp==1)
System.out.println("No fixed point in the array \n");
}
}```
```5
1 2 1 3 5```
`3`

### Complexity Analysis

#### Time Complexity

O(n) where n is the size of the array. Here we just traverse the array one time which leads us to linear time complexity.

All Unique Triplets that Sum up to a Given Value

#### Space Complexity

O(1) because we don’t use auxiliary space here.

## Approach 2(Binary Search)  In this case, we can use the this approach for the sorted array. Apply a binary search and check the condition for a fixed point. If find such a position then print that element else print “No fixed point in the array”.

### Algorithm

1. Assign the low variable and high variable to the starting and end of the array
2. Till low is less than high-
3. First check if the middle element is a fixed point or not, if yes print the mid element.
a. if the mid element value is less than the mid index. If yes, update low to mid +1
b. if the mid element value is greater than the mid index. If yes, update high to mid -1

### Implementation

#### C++ Program for Find a Fixed Point in a Given Array

```#include <bits/stdc++.h>
using namespace std;
int bin_search_fixed(int arr[],int low , int high)
{
while(low <= high)
{
int mid = low + (high - low)/2;

if(arr[mid] == mid)
return mid;

else if(arr[mid] < mid)
low = mid +1;
else
high = mid - 1;

}
return -1;
}
int main()
{
int N;
cin>>N;
int arr[N];
for(int i=0;i<N;i++)
{
cin>>arr[i];
}
int index = bin_search_fixed(arr,0,N-1);
if(index >= 0)
cout << arr[index]<<endl;

else
cout<<"No fixed point in the array \n";

return 0;
}```

#### Java Program for Find a Fixed Point in a Given Array

```import java.util.Scanner;
class sum
{
public static int bin_search_fixed(int arr[],int low , int high)
{
while(low <= high)
{
int mid = low + (high - low)/2;

if(arr[mid] == mid)
return mid;

else if(arr[mid] < mid)
low = mid +1;
else
high = mid - 1;

}
return -1;
}
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
int index = bin_search_fixed(a,0,n-1);
if(index >= 0)
System.out.println(a[index]);
else
System.out.println("No fixed point in the array");
}
}```
```5
1 2 1 6 5```
`No fixed point in the array`

### Complexity Analysis

#### Time Complexity

O(logn) where n is the size of the array. Here we use binary search which has logn time complexity.