Thread: Find the fixed point of an array ...i.e return i if a[i]=i..

Write a c program for the following

Find the fixed point of an array ...i.e return i if a[i]=i..


OBJECTIVE: Find the "fixed point" of an array

Input: an array A of *distinct* integers in ascending order.

(Remember that integers can be negative!) The number of

integers in A is n.
Output: one position i in the list, such that A[i]=i, if any exists.

Otherwise: "No".

method 1 :
If A [ i ] > i , we can ignore the right half of the array because

in right half ,for all j > i , we must have A [ j ] > j since A [ i ] >

i, as all the numbers are distinct.
Similarly , if A [ i ] < i, we can ignore the left half of the array

because in left half, for all j < i , we must have A [ j ] < j since A

[ i ] < i ,as all the numbers are distinct.

method 2:
n = size of array
take it=n/2

iterate till it>0&&it<n
if(A[it]>it)
it=it/2
else if(A[it]<it)
it+=it/2
else
return it

if loop returns nothing return error msg

I have tried to write the following code...but got infinite loop error
#includ

Code:

e<stdio.h>
#include<math.h>
main()
{
 int a[20];
int n,i,mid,low,high,j,temp;

 printf("\nEnter the Limit          : ");
 scanf("%d",&n);
 printf("\nEnter the numbers        : ");
 for(i=0;i<n;i++)
   scanf("%d",&a[i]);
 
 low=0;
     high=n-1;
   do
     {
      mid= (low + high) / 2;
     
  if(a[mid]==mid )
{

               printf("Present = %d \n",a[mid]);                 
}


      
       
       else if(a[mid]< mid)
             low = mid + 1;

    
    else  high = mid - 1;
continue;
    
        } while( low <= high);
}

Are you trying to be artistic with the indentation?

You'll want to fix the indentation if you want anyone to read your code.

Based on the text description, I would write this...

Code:

int FindFixedPoint(int *array, int size)
  { int i;

     for (i = 0; i < size; i++)
        if (array[i] == i)
          return i;

     return -1;  // no fixed point
}

Hint: if this if is true; do you not wish to break out of the loop?

Code:

      if(a[mid]==mid )
 
        {
 
          printf("Present = %d \n",a[mid]);                
 
        }