# Find a Fixed point in a given sorted array

## Given an array of n distinct elements which is sorted in ascending order, find the fixed point in the given array, where fixed point means the element value is same as the index

### Example1

input :

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

output :

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

### Example 2

Input : {2,7,9,3,10,8}

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

## Algorithm 1(Linear Search) :

Time Complexity : O(n)

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

## C++ Program

#include <bits/stdc++.h>
using namespace std;

int main()
{
int arr[] =  { -10, -5, 0, 3, 7 , 9 , 11 , 13}; //array
int N = sizeof(arr)/sizeof(arr[0]); //size of array

for(int i = 0; i < N; i++)
{
if(arr[i] == i)
{
cout << arr[i] << " is a fixed point in the array \n ";
return 0;
}
}
cout<<"No fixed point in the array \n";

return 0;
}

## Algorithm 2(Binary Search) :

Time Complexity : O(logn)

Assign the low variable and high variable to the starting and ending of the array
Till low is less than high
1. First check if the middle element is 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

## C++ Program

#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 arr[] =  { -10, -5, 0, 2, 3 , 4,  5,  7 , 11 , 13}; //array
int N = sizeof(arr)/sizeof(arr[0]); //size of array

int index = bin_search_fixed(arr,0,N-1);
if(index >= 0)
cout << arr[index] << " is a fixed point in the array \n ";

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

return 0;
}

Scroll to Top