## Decreasing-Increasing Array

### May 29, 2020

The student’s suggestion to use binary search that takes O(log *n*) time doesn’t work because every element of the array must be examined to determine if the array is in decreasing-increasing order. Here is our solution:

(define (sorted? pred? xs) (cond ((or (null? xs) (null? (cdr xs))) #t) ((not (pred? (car xs) (cadr xs))) #f) (else (sorted? pred? (cdr xs)))))

(define (decr-incr xs) (if (< (length xs) 3) #f (let ((pivot (apply min xs))) (let-values (((decr incr) (split-while (lambda (x) (not (= x pivot))) xs))) (if (and (not (null? decr)) (not (null? incr)) (sorted? >= decr) (sorted? <= incr)) pivot #f)))))

That’s O(*n*) even though it makes four passes through the input (in `length`

, `min`

and `split-while`

and the two pieces of `sorted?`

). Here are the example problems:

> (decr-incr '(10 10 10 8 8 6 4 4 3 12 13 22 31 40 59 68)) 3 > (decr-incr '(1 2 4 8 16 32 64)) #f

You can run the program at https://ideone.com/qTh5S7.

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.