[Java] Find minimum in rotated sorted array of unique elements

We've seen how to search for an element in a sorted array of unique element, which was rotated an unknown amount of times.

Now we want to find the minimum element in that array.

The approach is the same, however the minimum element can be in two places:

• at the beginning, if the array was not rotated of rotated enough times it went back to its initial state
• somewhere in the array AFTER a BIGGER element than itself

We can therefore do a binary search testing for this condition: which adjacent elements are such that the first is bigger than the second. When we find that pair, the second element will be the smallest.

This is because the array has unique elements and was sorted, therefore there is only one place where this pair exists and it's where the last and first meet.

If we view the array as a circle, a sorted array as last and first meeting at the very borders.

At each iteration of the search we have the following cases:

• a[mid] > a[mid + 1]: the smallest is in mid + 1
• a[floor] > a[mid]: a rotation happened and the split point will be on the left side, ceil = mid - 1
• otherwise the rotation is somewhere on the right, floor = mid + 1

This code runs in O(logN) time and constant space.

You can check my implementation of minimumRotatedSortedArray on my Gist along with some tests in MinimumRotatedSortedArrayJTests.