Find the number of times a Sorted array is Rotated

Question:

You are given an array that is rotated clockwise, you need to find the number of times the array is rotated.

Example 1:

array = {5, 6, 1, 2, 3, 4}

Output = 2 Times.

Why?

Because, the sorted array will be {1, 2, 3, 4, 5, 6} on first rotation it will be {6, 1, 2, 3, 4, 5} on the 2nd rotation {5, 6, 1, 2, 3, 4}.

Example 2:

array = {5, 1, 2, 3, 4}
Output = 1 times.

Solution:

If you observe the example carefully, the index of the smallest element of the array is the number of times the array has been rotated.

Method 1:

You can solve this by using linear search, to search for the smallest element of the array and return the index.

Method 2:

We can solve this program more efficiently by using modified binary search.

We know that, if an element is smaller, if the previous element to it is greater. If it is not greater, then there is no rotation.

There are 3 cases to be taken care:

Case 1: No rotation {1, 2, 3, 4, 5}

Case 2: Smallest element at the right half {3, 4, 5, 6, 1, 2}

Case 3: Smallest element at the left half { 6, 1, 2, 3, 4, 5}

 

Solution in C++

#include <iostream>
using namespace std;

int find_min(int arr[], int length) 
{
    int start = 0,  end = length - 1;

    while(start < end) 
    {
        if(arr[start] < arr[end]) 
            //return arr[start]; // un-comment this to get the smallest element in the array
            return start;

        int mid = (start + end)/2;
        if(arr[mid] > arr[end])
            start = mid + 1;
        else
            end = mid;
    }
    
    //return arr[start]; // un-comment this to get the smallest element in the array
    return start;
}
  

int main(void) 
{ 
    int arr[] = {5, 6, 1, 2, 3, 4}; 
    int size = sizeof(arr) / sizeof(arr[0]); 

    int rotation_index = find_min(arr, size);

    cout<<"The array is rotated for  " <<rotation_index<<" times"<<endl;

    return 0; 
} 

Output:

The array is rotated for 2 times