- #1

Jairo Rojas

- 17

- 0

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

Code:

```
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: