1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Log(n) algorithm

  1. Apr 2, 2016 #1
    1. The problem statement, all variables and given/known data
    Suppose you are given an array A of n distinct integers with the following property: There exists a unique index p such that the values of A[1 . . . p] are decreasing and the values of A[p . . . n] are is increasing. For instance, in the example below we have n = 10 and p = 4:
    A = [20, 18, 12, 10, 50, 51, 69, 94, 103, 111]
    Design a O(log n) algorithm to find p given an array A with the above property


    2. Relevant equations


    3. The attempt at a solution

    I just used the mergesort and compared the rightmost point of the left array with the leftmost point of the right array. The running time has to be logn I think.

    Code (Text):

    T(E[]Array,int first, int last, int index)
    {
    if(first<last)
    {
    int mid=(first+last)/2
    T(E,0,mid,index)
    T(E,mid+1,last,index)
    if(E[mid]<E[mid+1])
    index=mid
    return;
    }
    return;
    }[/B]
     
     
    Last edited: Apr 2, 2016
  2. jcsd
  3. Apr 3, 2016 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    You cannot use an unmodified sorting algorithm, those don't run in faster than linear time.

    Your function calls two functions with half the range each, that leads to a linear runtime if nothing else happens.
    Also, for every reasonable language, your function ignores whatever the inner function calls do, which means you do not get a reasonable output.

    The idea to compare two elements in the middle recursively is good, but you cannot do that everywhere. The comparison has to determine where to continue searching.
     
  4. Apr 3, 2016 #3
    how would you do it?. I think that to fix your inquiry about to determine if the function continues searching you just put the comparison part on top of the algorithm.
    Code (Text):

    T(E[]Array,int first, int last, int index)
    {
    if(first<last)
    {
    int mid=(first+last)/2
    if(E[mid]<E[mid+1])
    {
    index=mid
    return;
    }
    T(E,0,mid,index)
    T(E,mid+1,last,index)

    }
    return;
    }
    [/B]
     
  5. Apr 4, 2016 #4
    I think that now this is better.
    Code (Text):

    int initial_first
    int initial_last
    T(E[]Array,int first,int last,int index)
    mid=(first+last)/2    
    if(mid!=initial_first and mid!= initial_last )              
        if(Last-first==0)
             if(E[mid-1]>E[mid] and E[mid+1]>E[mid])
             index=mid
         else
           return;
        else if(E[mid-1]>E[mid] and E[mid+1]>E[mid])
         index=mid
         return;
        else if(E[mid-1]<E[mid] and E[mid+1]>E[mid])
         T(E[]Array,0,mid,index)
        else
          T(E[]Array,mid+1,last,index)
    else
    return;
    [\code]
     
  6. Apr 4, 2016 #5

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    The idea is right, but there are some things that need fixing. Where is the point in checking "if(E[mid-1]>E[mid] and E[mid+1]>E[mid]) " twice?
    If last-first=0, going down another layer of recursion does not make sense, but if you set index=mid you do not return - and otherwise you return with nothing.

    initial_first and initial_last are not initialized, but if they would you might return with nothing.
     
  7. Apr 5, 2016 #6
    hello, I am finding mid by reference.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted