Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We have $a_{1}<a_{2}<\dots <a_{p}$ and $a_p > a_{p+1}>\dots>a_{n}$. We want to find the maximum element $a_{p}$ of a unimodal sequence reading as few elements is possible.

I want to make an algorithm that solves this problem and find its execution time. I assume that the sequence is already in memory so to access one element takes $Ο(1)$ time.

Can someone help me with it?

A sequence $A = (a_{1} a_{2} \dots a_{n})$ is unimodal if there is such a $p$ , $1\leq p \leq n$.

I will appreciate links for further study.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

If you compare two neighbor elements, you can find out whether you're in the increasing or the decreasing part of the sequence. Now use binary search to find the apex.


In more detail: From the beginning we know that the index of the apex lies somewhere between $L=\frac 12$ and $H=n+\frac 12$, where the letters stand for Low and High limits. I'll be using half-integer limits for ease of exposition; in a practical implementation you would represent them with, say, the next larger integer.

Now, if it happens that $H-L=1$, then we know exactly where the apex is. The index of the apex is, of course, an integer, and we will have bracketed it by the half-integer above and below it. So in that case we're done.

Otherwise, let $M$ be a half-integer roughly midway between $H$ and $L$ -- that is, either $\frac{H+L}{2}$ or $\frac{H+L+1}{2}$, such that $M$ is an integer plus $\frac 12$. We now compare the two neighbor elements $a_{M-\frac 12}$ and $a_{M+\frac 12}$. If the former is larger, the apex must be between $L$ and $M$; otherwise the apex is between $M$ and $H$. Thus we can replace either $L$ or $H$ with $M$ and start over from the previous paragraph.

Each time we repeat the loop, the distance between $H$ and $L$ will have decreased, so $H-L$ will eventually reach $1$; the algorithm terminates. In fact, $H-L$ will approximately halve each time we have made a comparison, so the number of iterations will be around $\log_2 n$. That means that the number of array accesses is $2 \log_2 n$, which is quite an improvement over a linear scan.

It can be slightly improved by the more involved algorithm suggested by Tony K, but this will not affect the asymptotic (big-O) behavior of the algorithm.

share|improve this answer
    
+1 You beat me to it =). Also I didn't notice that this is a homework question; my answer is too detailed, so I deleted it. –  Srivatsan Nov 8 '11 at 16:08
    
How do you manage to give such answers? Experience? Studying? Because i struggle to understand them. Also this is not a real homework. It is a homework for myself. I am studying for university entrance exams. –  pleis_j Nov 8 '11 at 16:32
    
Do you mean you struggle to understand my answer, or that the problem was a struggle for you? I'd be happy to expand more if you need it. –  Henning Makholm Nov 8 '11 at 16:52
    
I mean that these things are new to me and in some cases (like this one) i can't find a "clear" answer. I dont have someone to explain it to me, so it would be great if you can do it. –  pleis_j Nov 8 '11 at 17:02
1  
As for how to find the answer, I'd call it experience -- but of course studying (and doing as many exercises as you can find) is one way to get experience. Here, it is clear that we can solve it on $O(n)$ time simply by looping through the array, so the interesting question is whether we can do it faster than that. Experience tells me that binary search is the most common way of finding something in an array in less than linear time, so it's natural to try if we can make that work here. Then we need a way to distinguish left of the target from right, which leads to comparing neighbors. –  Henning Makholm Nov 8 '11 at 17:02

Edited to add: I've just discovered that my idea is not new. This Wikipedia page describes the "Golden section search" for unimodal functions.


Binary search is not likely to give the best worst-case behaviour. I suspect that the fastest algorithm (with the fewest array accesses in the worst case) involves the golden ratio $\varphi = (1 + \sqrt 5)/2$. We can converge on the answer by reducing the interval that contains it by a factor of $\varphi$ for each array access. Roughly (ignoring rounding of array indexes to integers):

Start with $lo = 1, hi = n$, and $x_0 = n / \varphi$.

Then we have $p_{lo} < p_{x_0}$ and $p_{x_0} > p_{hi},$ and the ratio of the lengths of the two sub-intervals is $\varphi$. Call these two sub-intervals $L_0$ and $S_0$ (long and short). Now iterate as follows:

Choose array index $x$ to divide $L_r$ into two sub-intervals with lengths in the ratio $\varphi$ to $1$, so that the shorter of the two new sub-intervals is adjacent to $S_r$. Then set $S_{r+1}$ to be this shorter interval; and set $L_{r+1}$ to be either $S_r$, or the longer of the new sub-intervals, according as $p_x$ is greater or less than $p_{x_r}$. Then $x_{r+1}$ wil be $x_r$ (in the first case) or $x$ (in the second case). Because of the properties of $\varphi$, $L_{r+1}$ is the same length as $S_r$ in either case.

I'm not claiming that this algorithm is faster in the real world than binary search. There are too many fiddly details to get right. But I think it requires fewer array accesses (than any other algorithm) in the worst case.

share|improve this answer
    
+1 -- yes, your algorithm requires $\frac{1}{2\log_2\phi} \approx 0.72$ times as many array reads as mine in the asymptotic limit. But takes a bit of sketching to understand. –  Henning Makholm Nov 8 '11 at 17:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.