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