Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 2 of 2
11-08-2011, 06:00 AM #1
- Join Date
- Nov 2011
- Thanked 0 Times in 0 Posts
Find the fixed point of an array ...i.e return i if a[i]=i..
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.
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.
n = size of array
iterate till it>0&&it<n
if loop returns nothing return error msg
(Post new methods if any ...)
11-11-2011, 08:51 PM #2