Find a Fixed Point in a Given Array

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

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

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

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