Find pivot element in a sorted array

Problem Statement

Given a sorted array that has been rotated at some pivot point, find the pivot element. The pivot is the point where the array was rotated, i.e., the smallest element in the array (which is the starting point of the original sorted array).

Constraints:

• Array was originally sorted in ascending order
• Array is rotated at some unknown pivot
• All elements are distinct
• 1 ≤ n ≤ 10^5

Example:

• Input: arr = [4, 5, 6, 7, 0, 1, 2]
• Output: 4 (index of pivot element 0)
• Explanation: Original array was [0, 1, 2, 4, 5, 6, 7], rotated 4 times

Example 2:

• Input: arr = [3, 4, 5, 1, 2]
• Output: 3 (index of pivot element 1)

Example 3:

• Input: arr = [1, 2, 3, 4, 5]
• Output: 0 (no rotation, first element is the minimum)

Approach 1: Brute Force (Linear Search)

Intuition

Scan through the array to find where the sorted order breaks, i.e., where arr[i] < arr[i-1].

Algorithm

1. Traverse the array from index 1 to n-1
2. If arr[i] < arr[i-1], we found the pivot at index i
3. If no such point found, array is not rotated, pivot is at index 0

public class Solution {
    public int findPivot(int[] arr) {
        int n = arr.length;
        
        for (int i = 1; i < n; i++) {
            if (arr[i] < arr[i - 1]) {
                return i;
            }
        }
        
        // No rotation, minimum is at index 0
        return 0;
    }
    
    public int findMinimum(int[] arr) {
        int n = arr.length;
        
        for (int i = 1; i < n; i++) {
            if (arr[i] < arr[i - 1]) {
                return arr[i];
            }
        }
        
        return arr[0];
    }
}

Complexity Analysis

• Time Complexity: O(n) - May need to scan entire array
• Space Complexity: O(1) - No extra space

Approach 2: Binary Search (Optimal)

Intuition

The minimum element is the only element that is smaller than its previous element. Use binary search to find this point efficiently.

Key Observations:

1. If arr[mid] > arr[right], minimum is in right half
2. If arr[mid] <= arr[right], minimum is in left half (including mid)
3. We're essentially searching for the first element of the original sorted array

Algorithm

1. Initialize left = 0, right = n - 1
2. While left < right:
   • Calculate mid
   • If arr[mid] > arr[right], search right half: left = mid + 1
   • Else search left half: right = mid
3. Return left (index of minimum)

public class Solution {
    public int findPivot(int[] arr) {
        int n = arr.length;
        int left = 0, right = n - 1;
        
        // If array is not rotated
        if (arr[left] <= arr[right]) {
            return 0;
        }
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            // If mid element is greater than rightmost,
            // minimum is in the right half
            if (arr[mid] > arr[right]) {
                left = mid + 1;
            }
            // Minimum is in the left half (including mid)
            else {
                right = mid;
            }
        }
        
        return left;
    }
    
    // Alternative: Find the maximum element (last of first sorted part)
    public int findMaxPivot(int[] arr) {
        int minIdx = findPivot(arr);
        return minIdx == 0 ? arr.length - 1 : minIdx - 1;
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(log n) - Binary search
• Space Complexity: O(1) - Only using pointers

Approach 3: Finding Pivot with Peak Detection

Intuition

Instead of finding minimum, find the maximum element (peak) which is immediately before the minimum.

public class Solution {
    // Find index of maximum element (peak before pivot)
    public int findPeakPivot(int[] arr) {
        int n = arr.length;
        int left = 0, right = n - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            // Check if mid is the peak
            if (mid < n - 1 && arr[mid] > arr[mid + 1]) {
                return mid;
            }
            // Check if mid-1 is the peak
            if (mid > 0 && arr[mid] < arr[mid - 1]) {
                return mid - 1;
            }
            
            // Decide which half to search
            if (arr[mid] >= arr[left]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        // No rotation
        return n - 1;
    }
}

Handling Duplicates

When array contains duplicates, worst case becomes O(n):

Applications

Key Takeaways

1. Pivot = Minimum Element: In a rotated sorted array, pivot is where rotation happened
2. Binary Search on Property: We search for the transition point, not a specific value
3. Comparison Strategy: Compare with rightmost element to decide search direction
4. Two Views: Can find either minimum (start of original) or maximum (end of first part)
5. Rotation Count: Pivot index equals the number of rotations
6. Duplicates: Make the problem harder with O(n) worst case
7. Foundation Problem: This is the basis for many rotated array problems