Get the rotation count in sorted rotated array

Problem Statement:

You are given an array, you need to check if the array is sorted and rotated.

Example:

array = {6, 7, 1, 2, 3, 4, 5}
Output; True

array = {1, 2, 3, 4, 5}
Output; False
Because it is not rotated

Solution:

We can solve it by modified binary search.

What we do here is, once we find the middle index,

1. If mid index is less than end index, we check with the middle element is greater than the to it’s element to its right. If yes return the mid index.
Example:

{4, 5, 6, 7, 1, 2, 3}
Here mid element is 7 and is greater than the element towards its right. Hence return that index.

2. If mid index is greater than start index, we check with the middle element is smaller than the to it’s element to its left. If yes return the mid -1 index.
Example:

{4, 5, 1, 2, 3}
Here mid element is 1 and is smaller than the element towards its left. Hence return mid-1 index.

3. If both the values are not satisfied then we need to move to right half or left half accordingly

Solution in C++

#include <iostream>
using namespace std;


int is_array_sorted_and_rotated( int arr[], int len)
{
    int start = 0;
    int end = len - 1;

    while (start <= end)
    {
        int mid = (start + end) / 2;

        if (mid < end && arr[mid + 1] < arr[mid])  
        { 
            return mid; 
        } 
        
        // for the case {4, 5, 1, 2, 3} 
        if (mid > start && arr[mid] < arr[mid - 1]) 
        { 
            return mid - 1; 
        } 

        // jump left half or right half
        if (arr[start] > arr[mid])
        {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }

    return -1;
}

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

    if(result)
    {
        cout<<"Array is sorted and rotated"<<endl;
    } else {
        cout<<"Array is NOT sorted or NOT rotated"<<endl;
    }

    return 0; 
} 

Output:

Array is sorted and rotated