Find Rotation Count in Rotated Sorted Array in C

A rotated sorted array is created by shifting elements of a sorted array.

The number of rotations is equal to the index of the smallest element.

We can efficiently find this using binary search.

Concept Overview

Rotation count indicates how many times the array has been rotated.

Example: [1,2,3,4,5] → rotated 2 times → [4,5,1,2,3]

Here, the smallest element (1) is at index 2.

Problem Statement

Given a rotated sorted array, find how many times it has been rotated.

Example

Input:
Array: 4 5 6 7 0 1 2

Output:
Rotation Count: 4

Approach (Binary Search)

1. Initialize low = 0 and high = n-1.

2. While low < high:

3. Find mid = (low + high) / 2.

4. If arr[mid] > arr[high], pivot is in right half.

5. Else, pivot is in left half.

6. Continue until low == high.

7. Return index (low) as rotation count.

C Program

#include <stdio.h>

int findRotationCount(int arr[], int n) {
    int low = 0, high = n - 1;

    while (low < high) {
        int mid = (low + high) / 2;

        if (arr[mid] > arr[high])
            low = mid + 1;
        else
            high = mid;
    }

    return low;
}

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

    int rotations = findRotationCount(arr, n);

    printf("Rotation Count: %d", rotations);

    return 0;
}

Output

Rotation Count: 4

Detailed Explanation

The algorithm identifies the smallest element using binary search.

If mid element is greater than the last element, pivot lies on the right.

Otherwise, pivot lies on the left.

The final index gives the rotation count.

Time and Space Complexity

Time Complexity: O(log n)

Space Complexity: O(1)

Applications

Used in cyclic data analysis.

Helps optimize search operations in rotated arrays.

Advantages

Efficient logarithmic time solution.

Works well for large datasets.

Limitations

Assumes no duplicate elements.

Requires sorted rotated array.

Improvements You Can Make

Handle duplicate values.

Combine with search operation for optimization.

Detect rotation direction.

Understanding rotation count helps solve many advanced binary search problems efficiently.