# Log(n) algorithm

1. Apr 2, 2016

### Jairo Rojas

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. Apr 3, 2016

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

3. Apr 3, 2016

### Jairo Rojas

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]

4. Apr 4, 2016

### Jairo Rojas

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]

5. Apr 4, 2016

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

6. Apr 5, 2016

### Jairo Rojas

hello, I am finding mid by reference.