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;
}
Try It

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;
}
Try It


Next > < Prev
Scroll to Top