2
$\begingroup$

I have found out how to find the maximum of a "bitonic" array. The problem is as follows.

An array is bitonic if it is comprised of an increasing or decreasing sequence of integers followed immediately by a decreasing or increasing (respectively) sequence of integers. Write a program that, given a bitonic array of n distinct integer values, determines whether a given integer is in the array. Use O(lg n) compares in the worst case.

This can easily be done using a modified binary search.

I was wondering if one could find the maximum of "tritonic" array.

A tritonic array is, naturally, an array with an increasing run of elements, then decreasing, then finally increasing again or decreasing->increasing->decreasing.

I've tried a similar binary search approach but to no awail.

I would really appreciate some pseudocode or python outlining the algorithm. Specifically, I'm looking for an O(lg n) algorithm.

I am asking about this because I believe this may relate to a problem I'm having implementing Chan's algorithm, which I asked about here.

NOTE: bitonic arrays are also called unimodal and rotated sorted arrays.

EDIT: This paper describes how to find the maximum of a specific bimodal/tritonic array

$\endgroup$
2
  • 1
    $\begingroup$ Does increasing mean strictly increasing ($<$), or non-decreasing ($\le$)? $\endgroup$
    – D.W.
    Feb 29 at 4:11
  • 1
    $\begingroup$ @D.W. It means strictly increasing and decreasing means strictly decreasing $\endgroup$
    – user716881
    Feb 29 at 12:30

1 Answer 1

1
$\begingroup$

You can't. It's not possible to do this in $O(\log n)$ time.

Consider the following two possibilities for the tritonic array:

  1. We have an array $A^1$ that contains the values $1,2,3,4,\dots,n$, except that at index $i$, we have the value $2n$.

  2. We have an array $A^2$ that contains the values $1,2,3,4,\dots,n$, except that at index $i$, we have the value $2n+1$.

Intuitively, if the algorithm does not read the $i$th entry in the array, then it cannot distinguish between these two arrays. An algorithm that runs in $O(\log n)$ time can only examine $O(\log n)$ entries of the array. So, the chances that it happens to examine the $i$th entry is vanishingly small ($O((\log n)/n)$, since every other array entry is identical in both arrays and gives no information about $i$ or whether we're dealing with $A^1$ or $A^2$). Consequently, any such algorithm can't be correct most of the time at finding the maximum of the input array.

You can formalize this using an adversary algorithm. Let $A^0$ denote the array that contains the values $1,2,3,\dots,n$. For a deterministic algorithm, we imagine running the algorithm, to find the maximum of the input array $A^0$, examine which entries it reads, then after it completes, pick an index $i$ such that it hasn't read entry $i$ (one must exist: since it runs in $O(\log n)$ time, it examines at most $O(\log n)$ entries, so there must exist some entry that hasn't been examined). We can see that the algorithm must do exactly the same steps and produce the same output, regardless of whether it is run on $A^0$, $A^1$, or $A^2$, since all three arrays are identical on the entries it reads. Now the algorithm must produce the wrong answer on at least one of those inputs. Therefore the algorithm is not correct.

This can be generalized to prove that no randomized algorithm running in $O(\log n)$ time exists, either.

$\endgroup$
4
  • 2
    $\begingroup$ As written your proof does not work for what the OP asks, which is finding the maximum of the array, not finding a specific value. Regardless of whether you're dealing with $A^1$ or $A^2$, the maximum is $n$. $\endgroup$
    – orlp
    Mar 2 at 19:15
  • $\begingroup$ @orlp, good point! Thank you! I've edited my answer to match the problem statement and fix this flaw. Thanks for pointing that out. $\endgroup$
    – D.W.
    Mar 2 at 21:51
  • $\begingroup$ @D.W. What is the reason for using index i and i + 1? Couldn't both A^1 and A^2 have index i swapped and the proof would be simpler? $\endgroup$
    – Tyilo
    Mar 6 at 19:17
  • 1
    $\begingroup$ @Tyilo, You're absolutely right. Sorry about that. My proof had unnecessary complications. I've edited my answer along the lines you suggest, to simplify the proof. Thank you for pointing that out and helping to improve this answer. $\endgroup$
    – D.W.
    Mar 6 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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