Find middle element in a circularly sorted array

Given a circularly sorted array, find its middle element in best possible time.

A circularly sorted array is an array that is obtained by shifting an array k times. For example, the following is a circularly sorted array,

[5, 6, 7, 8, 9, 1, 2, 3, 4]

If you sort this array and find the middle element it will be 5. But then, sorting is a painful operation which will take O(nlogn) timing. So it is out of the equation right away. If you closely observe this problem, it is enough to find the shifting index, the place where the sorting varies. For example, the shifting index in the above example is 5.  Once that is found, then it is a matter of applying the bias over the length.

This program can be attacked in a recursive manner. Take the first and last elements in the array and compare them. If they are sorted, then the last element is greater than the first element. If this condition is not met, we will have to divide this array into two halves and try applying the same logic. If you do this, at some point you will arrive at a situation where you are left with only two elements or lesser. The end value is the shift index. Once the shift index is found, it is easy to find the middle element(s) for odd and even cases. Java code is below.

Leave comments if something is unclear.

Cheers!
Braga