## Decreasing-Increasing Array

### May 29, 2020

Today’s task is somebody’s homework:

Given an array of integers, determine if it is in decreasing-increasing order, with some initial segment of the array in decreasing order and the remainder of the array in increasing order. If the array is in decreasing-increasing order, return the pivot element (the minimum element in the array); otherwise, return an indication the array is not in decreasing-increasing order. Array elements may be duplicated. For example, the array (10 10 10 8 8 6 4 4 3 12 13 22 31 40 59 68) is in decreasing-increasing order, with pivot element 3, but the array (1 2 4 8 12 32 64) is not in decreasing-increasing order.

The student who asked the question suggests a solution using binary search that takes O(log *n*) time, but can’t get it to work.

Your task is to write a program to determine if an array is in decreasing-increasing order as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

It is hard to see how this can be done in O(logn), as all elements will have to be inspected. For example: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 is decreasing-increasing. But change the 7th from 4 to 6 and it is not decreasing-increasing any more.

Pretty straight-forward problem. Here is my take on it in Julia 1.4.1: https://pastebin.com/XpBgPV6J

The code could use improvements so I’ll look into it further. However, as a first draft it should be acceptable (works well in relatively small arrays). Cheers!

As you say, a log(n) solution doesn’t seem possible, but a single pass and O(1) storage should be enough.

Here is a solution in R7RS Scheme that uses only a single pass and

detects an invalid input as early as possible without examining the

rest of the input. So it has excellent expected running time on

random inputs. :-) O(log n) is impossible for worst-case running time

because a valid sequence can be turned into an invalid one by changing

any element that the algorithm does not inspect.

@programmingpraxis, for your solution,

`(decr-incr '(1 2 4 8 16 32 64))`

returns`#f`

, but`(decr-incr '(64 32 16 8 4 2 1)`

, returns 1. If the lack of a decreasing prefix does not succeed, my expectation is that the lack of an increasing suffix would also not succeed.Here’s a solution in C.

Example usage:

There’s a bug in my earlier solution. Calling the code with

`3 3 5`

returns`3`

, whereas I think this should return no solution. An update to line 9 addresses this issue.In Python using 3 states. INIT means no decrease happend yet. DECREASED means there was a decrease and INCREASE means there was an increase (after a decrease). The logic is simple. If the value does not change, there is nothing to do. The minimum value can be set if the state goes from DECREASED to INCREASED.

Here’s a Haskell version.

A solution in Racket.

As observed before, we cannot determine whether or not the array given is in Decreasing-Increasing order without examining all of the array elements. Doing so, forces a O(n) solution. I think that the wording was off however, and that we should assume that the array is in Decreasing-Increasing order, then throw an error iff we detect a contradiction while searching for the pivot. Assuming that the array is ordered, makes this a more interesting problem. However, in the worst case, every element is the same. Any algorithm that tried to find the pivot in such an array would still be required to examine all of the elements. Accordingly, the worst case performance is still O(n). But we can do better than this

on average:This leads to traces such as the following:

Which exhibit O(log(n)) behavior. I suspect that this is what the instructor meant.