346. Find the Pivot Element in a Sorted Rotated Array

An ascending array of n distinct integers was rotated at some unknown pivot. Find the index of the pivot element - the smallest element in the array (equivalently, the point where the ascending order 'breaks'). If the array wasn't rotated at all, the pivot index is 0.

Input: The first line contains an integer n. The second line contains n space-separated distinct integers. Output: Print a single integer - the index of the pivot (smallest) element.

1 <= n <= 10^5, all elements distinct

Comparing against arr[hi] (rather than arr[lo]) is a specific, deliberate choice that correctly handles the edge case of a search range with only 2 elements - a common source of off-by-one bugs if the comparison endpoint isn't chosen carefully.

An array that was originally sorted ascending got 'rotated' at some point - find the index where the ascending order breaks (the smallest element). Brute force: Scan the array linearly looking for the one place where arr[i] > arr[i+1] - this costs O(n), unnecessary given the array's underlying (rotated) sorted structure. Optimised: Comparing arr[mid] against arr[hi] at each step reveals which HALF of the current search range is genuinely sorted (and therefore can't contain the pivot, since a sorted half's first element is always <= its last) - discarding that half and recursing into the other narrows down to the pivot in O(log n).

Apply binary search by comparing the middle element to the first element of the current search range: if arr[mid] >= arr[low], the left half is itself in ascending order, so the pivot (if present in this range) must lie further right, and the search narrows into (mid+1..high); otherwise the pivot lies within low..mid instead. Because a rotated ascending array is always made of at most two sorted runs, this reaches the pivot in logarithmic time, though the "compare to low" invariant needs a little extra care around ranges that are already fully sorted. Time: O(log n) Space: O(1)

Scan through the array from left to right comparing each element to the one right after it; the first place where an element is greater than its successor marks the break in the ascending order, and the next index is the pivot (the smallest element). If no such break is ever found, the array was never rotated and the pivot index is 0. Time: O(n) Space: O(1)

Apply the same binary search idea but compare the middle element to the current high (rightmost) element instead of the low one: if arr[mid] > arr[high], the minimum must lie strictly right of mid, so search (mid+1..high); otherwise the minimum is at mid or to its left, so search (low..mid). This invariant is simpler and self-correcting, naturally handling an already-sorted (unrotated) range without special-casing, and it is asymptotically the best possible, since locating an unknown pivot among n elements by comparisons requires at least Omega(log n) of them. Time: O(log n) Space: O(1)

1. If the array's first element is already <= its last element, there was no effective rotation - the pivot index is 0. 2. Otherwise, binary search: compare arr[mid] to arr[hi] (the current right boundary). 3. If arr[mid] > arr[hi], the pivot (break point) must be strictly to the RIGHT of mid; otherwise, it's at mid or to the LEFT.

Time: O(log n) - a modified binary search. Space: O(1) - just a few pointer variables.

Test n = 1 (pivot index 0), an array that wasn't rotated at all (pivot index 0), and n = 10^5 for performance.

Be ready to connect this directly to 'Search in a Rotated Sorted Array' - finding the pivot first is one classic way to reduce that harder search problem into two separate binary searches on genuinely sorted sub-ranges.