Is there a O(log n)-time algorithm to find the maximum element of a circular shift of a sorted array?

Question

Consider this problem: You are given an array $A$ (of distinct integers) of one out of the following four types:

• Ascending (e.g., 1,2,4,6);
• Descending (e.g., 6,4,2,1);
• Ascending rotated (a non-trivial circular shift of an ascending array, e.g., 4,6,1,2);
• Descending rotated (a non-trivial circular shift of an descending array, e.g., 4,2,1,6).

The task is to determine the type and the maximum element of $A$.

Since $A$ is "sorted", is there a $O(\log n)$-time approach or is the best possible time complexity $O(n)$, as suggested in the link?

Answer 1

Let $A = \langle a_1, \dots, a_n \rangle$ be the input array. I will only consider the case $n \ge 3$, otherwise the problem is trivial.

The key property is that the order relation between all but one pair of consecutive elements modulo $n$ in $A$ will be "greater than" if $A$ is some circular shift of an increasing array (possibly the trivial shift by $0$), and "less than" if $A$ is some circular shift of a decreasing array. Examining the first and last elements suffices to determine if the shift is trivial or not.

In practice you can determine the type of $A$ in constant time, as follows:

• Look the majority value $x$ among $\textrm{sign}(a_1-a_n)$, $\textrm{sign}(a_2-a_1)$, and $\textrm{sign}(a_3-a_2)$.

• If $x = +1$ then $A$ is some circular shift of an increasing array. If $\textrm{sign}(a_1-a_n)=-1$, $A$ is of type "ascending", otherwise it is of type "ascending rotated".

• If $x = -1$ then $A$ is some circular shift of a decreasing array. If $\textrm{sign}(a_1-a_n)=1$, $A$ is of type "descending", otherwise it is of type "descending rotated".

As for returning the maximum, I will only discuss the case in which $A$ is a circular shift of an increasing array (the complementary case is handled similarly). Notice that, if the maximum element is in some position $a_j$, then all $a_1, \dots, a_j$ are larger than or equal to $a_1$, while all ements $a_{j+1}, \dots, a_n$ are smaller than $a_1$. This allows you to binary search for the last element that is larger than or equal to $a_1$, i.e., $a_j$.

Answer 2

if we are given with first two cases i.e Ascending sorted array and descending sorted arrays we can simply find the difference b/w last element of array and first element of array i.e (last element of array - first element of arrays)if difference is positive then it is ascending order and maximum element is the element at last index of array (in ascending sorted arrays ) and vice versa. it takes just 0(1) in that case.