How many times an array is rotated?

The problem is to find how many times a given array is rotated.

for eg: If 1 2 4 5 6 7 is rotated to "4" times to make it like this 4 5 6 7 1 2

Now if you look closer, the number of times an an array is rotated is simply the index of the smallest element in the array. In our example it is 4(index of 1).

So now we just have to find the smallest element in the array. Let's call this smallest element as the pivot element from now on.

One of the way to do that is to simply to do linear search and look for pivot element, when found just return the index of that. But that would take O(n) in worst case.

There is actually one more way to do that in O(log(n)) time. The idea is to use Binary search with some modifications.

As you see the pivot element has a special property; it is the only element in the array which is smaller than both it's previous and next element;

in our example "1" being the pivot element, it is smaller than both 7 (previous) and 2 (next).

The following code finds the pivot element:

CODE:

int pivot( vector<int> A)

{

int len = A.size(),low = 0, high = len-1;
while(low <= high){
if(A[low] <= A[high]) return low;  // Array is already sorted so first element is the pivot element
int mid = (low + high)/2;
int next = (mid+1)%len, prev = (mid+len-1)%len;  // % is done just because it is a circular sorted list
if(A[mid] <= A[next] && A[mid] <= A[prev]) //   the condition for the pivot element
return mid;
else if (A[mid] <= A[high]) //  This means right half is sorted so we need to look in the left half.
high = mid - 1;
else if (A[mid] >= A[low]) //  This means left half is sorted so we need to look in the right half.
low = mid + 1;
}
return -1;

}