Finding minimum in alternating sequence with ⌈n/2⌉ comparisons

[evinda]

Hello! (Smile)

We have a sequence of numbers $A=(a_1, a_2, \dots, a_n), n \geq 3$, for which, it stands the following:

$$\forall i \text{ with } 2 \leq i \leq n-1:$$

either
$$ 1. a_{i-1}<a_i \text{ and } a_i>a_{i+1}$$

or
$$2. a_{i-1}>a_i \text{ and } a_i<a_{i+1}$$

I have to write an algorithm, that finds the minimum element of $A$ with at most $\lceil \frac{n}{2} \rceil$ comparisons.

So, we have to compare the first two elements and if the first is smaller, we will just look at the elements of the odd positions, in order to find the minimum, and if the second element is smaller we will look at the elements of the even positions, right? (Thinking)

Then, how will we find the minimum of the remaining elements we are looking at? Using a while or is there an other way? (Thinking)

 

[magneto1]

I have to write an algorithm, that finds the minimum element of $A$ with at most $\lceil \frac{n}{2} \rceil$ elements.

Do you mean $\lceil \frac{n}{2} \rceil$ comparisons?

 

[evinda]

Do you mean $\lceil \frac{n}{2} \rceil$ comparisons?

Yes, I am sorry... (Blush)