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

1. 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);
}```

2. Are you trying to be artistic with the indentation?

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

3. Sorry for that mistake.
I have re posted the code in a more readable form
Code:
```#include<stdio.h>

#include<math.h>
main()

{
int a[20];
int n,i,mid,low,high;

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

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

4. 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
}```

5. > I have tried to write the following code...but got infinite loop error
So what do you think the continue statement is doing for you?

Have you tried running (and single stepping) the code in a debugger to see if high/low are actually converging on a mid-point in the array?

6. 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]);

}```