...

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



sr4cafe
11-08-2011, 06:00 AM
Write a C program for the following algorithm

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 k 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

(Post new methods if any ...)

bobleny
11-11-2011, 08:51 PM
Oh that's cool.

Did you need help with something?



EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum