Find p in a Sorted Array with Unique Property | O(log n) Algorithm

[Jairo Rojas]

Homework Statement

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

Homework Equations

The Attempt at a Solution

[/B]
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.

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]

 

[mfb]

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.

 

[Jairo Rojas]

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.

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.

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]

 

[Jairo Rojas]

how would you do it?

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.

I think that now this is better.

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]

 

[mfb]

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.

 

[Jairo Rojas]

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.

hello, I am finding mid by reference.