Find the least element in an array, which has a pattern

Question

An array is given such that its element's value increases from 0th index through some (k-1) index. At k the value is minimum, and than it starts increasing again through the nth element. Find the minimum element.

Essentially, its one sorted list appended to another; example: (1, 2, 3, 4, 0, 1, 2, 3).

I have tried all sorts of algorithm like buliding min-heap, quick select or just plain traversing. But cant get it below O(n). But there is a pattern in this array, something that suggest binary search kind of thing should be possible, and complexity should be something like O(log n), but cant find anything. Thoughts ??

Thanks

Answer 1

No The drop can be anywhere, there is no structure to this.

Consider the extremes

1234567890
9012345678
1234056789
1357024689

It reduces to finding the minimum element.

Answer 2

Do a breadth-wise binary search for a decreasing range, with a one-element overlap at the binary splits. In other words, if you had, say, 17 elements, compare elements

0,8
8,16
0,4
4,8
8,12
12,16
0,2
2,4

etc., looking for a case where the left element is greater than the right.

Once you find such a range, recurse, doing the same binary search within that range. Repeat until you've found the decreasing adjacent pair.

The average complexity is not less than O(log n), with a worst-case of O(n). Can anyone get a tighter average-complexity estimate? It seems roughly "halfway between" O(log n) and O(n), but I don't see how to evaluate it. It also depends on any additional constraints on the ranges of values and size of increment from one member to the next.

If the increment between elements is always 1, there's an O(log n) solution.