Understanding finding the minimum in a sorted rotated array

Binary search exponentially speeds up the search for values in a sequence by exploiting the order of items in it. There are many problems that may not be solvable by direct application of binary search, but by algorithms that use the same principle to reduce the size of the problem space by half in each iteration. One such problem is to find the minimum in a sorted rotated array.

A sorted rotated array is one where a sorted array is rotated in either direction by a certain number of times. A single rotation shifts every item one position in the chosen direction (left or right), with the item that falls off one end wrapping around to the other end. For example, right rotating [1, 2, 3, 4, 5] once produces [5, 1, 2, 3, 4]. The minimum item in a sorted rotated array is called the pivot item. Finding the minimum (pivot) item in a sorted rotated array is a classical problem that can be solved by exploiting the semi-sorted nature of the sequence.

Finding the minimum in a sorted rotated array

It is easy to see that a sorted rotated array is made up of two sorted sequences that come one after the other. The minimum value in a sorted rotated array is also called its pivot item, and it is the first item in the second sorted sequence.

Given below is how the sorted rotated array from the example looks when its values are plotted on a Cartesian plane.