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

2 replies · 2K views · last reply
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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)
 
Last edited:
evinda said:
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?
 
magneto said:
Do you mean $\lceil \frac{n}{2} \rceil$ comparisons?

Yes, I am sorry... (Blush)