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.

Pages: 1 2