Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 2 of 2
  1. #1
    New to the CF scene
    Join Date
    Nov 2011
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Question 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.

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

  • #2
    Regular Coder bobleny's Avatar
    Join Date
    May 2007
    Posts
    258
    Thanks
    3
    Thanked 11 Times in 11 Posts
    Oh that's cool.

    Did you need help with something?
    --www.firemelt.net--
    * No good deed goes unpunished.
    * Cheer up, the worst has yet to come...


  •  

    Tags for this Thread

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •