Find Pivot Index in Rotated Sorted Array in C

In a rotated sorted array, the pivot is the index where the rotation occurs.

It is also the index of the smallest element in the array.

Finding the pivot efficiently helps solve many problems like searching and rotation count.

Concept Overview

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

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

The pivot is the position of the smallest element (1).

Problem Statement

Given a rotated sorted array, find the index of the smallest element.

Example

Input:
Array: 4 5 6 7 0 1 2

Output:
Pivot Index: 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. Otherwise, pivot is in left half (including mid).

6. Repeat until low == high.

C Program

#include <stdio.h>

int findPivot(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 pivot = findPivot(arr, n);

    printf("Pivot Index: %d\n", pivot);
    printf("Smallest Element: %d", arr[pivot]);

    return 0;
}

Output

Pivot Index: 4
Smallest Element: 0

Detailed Explanation

The algorithm compares middle element with the last element.

If mid element is greater, pivot must be on the right side.

Otherwise, pivot lies on the left including mid.

This narrows the search space logarithmically.

Time and Space Complexity

Time Complexity: O(log n)

Space Complexity: O(1)

Applications

Used in searching rotated arrays.

Helps find number of rotations.

Useful in optimization and cyclic problems.

Advantages

Efficient binary search approach.

Works well for large datasets.

Limitations

Assumes no duplicate elements.

Requires sorted rotated array input.

Improvements You Can Make

Extend to handle duplicate values.

Use pivot to perform faster search operations.

Find rotation count using pivot index.

Understanding pivot detection is key to mastering rotated array problems in C.