4
$\begingroup$

We have $a_{1} 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.

3 Answers 3

4

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.

  • 0
    Here is what i did. `binary_search(l,r,m){m = (l+r)/2;i$f$(a[m]a[m-1]){l=m+1;m=(l+r)/2;binary_search(l,r,m)}i$f$(a[m]>a[m+1] && a[m]>a[m-1]){r=m-1;m=(l+r)/2;binary_search(l,r,m)}if(a[m>a[m-1]){return a[m];}}`2011-11-08
3

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.

  • 0
    +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.2011-11-08
0

Henning Makholm's answer is reminiscent the concept of a binary search on the "derivative" of a function, which in a discrete sequence is the difference between two neighboring values. In the case of a continuous function or maybe one which getting neighbors is expensive, there exists a simpler method than Fibonacci search called a ternary search.

In essence, it considers 3 intervals. Call 2 points $m_1,m_2$ in between the interval bounds $l$ and $h$ such that $l. If $f(m_1), the maximum can't lie in $[l,m_1]$ so the search is repeated on the interval $[m_1,h]$. By symmetry, if $f(m_1)>f(m_2)$, the search is repeated on $[l,m_2]$. Wikipedia notes that if $f(m_1)=f(m_2)$, the search can be repeated on $[m_1,m_2]$ or be considered in one of the two previous cases. The search ends when the interval is within a desired maximum size ($1$ in the case of a discrete sequence).