Find a sequence in an unsorted list

user_8074646 0
Viewed 72

So, I am given an unsorted list A = (a1, a2, ..., an) with n distinct elements. My goal here is to find the middle index i (1 <= i <= n) of a sequence where ai-1 < ai and ai > ai+1. The algorithm should run in O(log(n)) worst case. It is also given that a0 = an+1 = -inf.

So basically i need to find an index surrounded by smaller number than itself, such as {1,5,3}, where 1 and 3 are smaller than 5.

Example:

Input: A = {1, 2, 4, 5, 3, 7, 6}

Output: 4 (because of the sequence {4, 5, 3})

This algorithm would be extremly easy if the worst case was to be O(n), where a simple for-loop could check that sequence, but I'm having a hard time with the fact that it needs to run worst case O(log(n)).

algorithm
1 Answers

First, note that if you have three elements a_i, a_j, a_k with i<j<k and a_j > a_i and a_j > a_k, then there must be a peak between i and k. The proof is easy: the maximum value that lies between a_i and a_k must be a peak, and it can't be either of the endpoints.

You can use this observation to solve the problem in logarithmic time.

We'll keep three values: x, y, z such that x<y<z and a_y > a_x and a_y > a_z. At the start, initialize x, y, z to 0, (n+1)/2, n+1. (The conditions will hold, because a_0 = a_(n+1) = -inf).

Now consider the triples (x, (x+y)/2, y), ((x+y)/2, y, (y+z)/2), (y, (y+z)/2, z)). One of these triples can serve as our next (x, y, z). (The proof is easy, but I'll leave it to you).

This process halves the range searched each time, and we stop when we're down to a small interval (say z-x < 5), at which point the peak is at most 1 or 2 elements.

user_14007930
Related