How to determine if a sequence is bitonic?

Question

A sequence is bitonic if it monotonically increases and then monotonically de- creases, or if it can be circularly shifted to monotonically increase and then monotonically decrease. For example the sequences (1, 4, 6, 8, 3, −2) , (9, 2, −4, −10, −5) , and (1, 2, 3, 4) are bitonic, but (1, 3, 12, 4, 2, 10) is not bitonic.

How can it be determined if given sequence is bitonic?

I have the following opinion. We can walk till n/2, where n is the length of the array, and check if

(a[i] < a[i + 1]) and (a[n - i - 1] < a[n-1 - (i + 1)]) 

Is this correct?

Answer 1

A bitonic sequence:

 /\ /  \     \/ 

Not a bitonic sequence:

 /\     /  \  / (higher than start)     \/ 

Obviously if the direction changes more than two times we cannot have a bitonic sequence.
If the direction changes less than two times, we must have a bitonic sequence.

If there are two changes in direction, we MAY have a bitonic sequence. Consider the two ascii images above. Clearly a sequence with two changes in direction will match one of the patterns (allowing for a reflection). Thus, we set the initial direction by comparing the first and last elements. Since these can be the same, we use the first element that is not equal to the last element.

Here is an implementation in Java:

public static Boolean bitonic(int[] array) {     if (array == null) return false;     if (array.length < 4) return true;     Boolean dir;// false is decreasing, true is increasing     int pos = 0, switches = 0;     while (pos < array.length) {         if (array[pos] != array[array.length - 1])             break;         pos++;     }     if (pos == array.length) return true;     //pos here is the first element that differs from the last     dir = array[pos] > array[array.length - 1];     while (pos < array.length - 1 && switches <= 2) {         if ((array[pos + 1] != array[pos]) &&            ((array[pos + 1] <= array[pos]) == dir)) {             dir ^= true;             switches++;         }         pos++;     }     return switches <= 2; }