Find pivot element in a sorted array

The problem, simply

Take a sorted array of different numbers, like [0, 1, 2, 4, 5, 6, 7]. Cut it somewhere and move the front part to the back: [4, 5, 6, 7, 0, 1, 2]. This is a rotated sorted array.

Find the turning point. It is the one place where a number is followed by a smaller one: the biggest number (the pivot) sits right before the smallest. Return the index of the smallest number. That index is also how many times the array was turned, and the pivot is the box just before it. If the array was not turned at all, return 0.

A story to remember it

Picture it

Examples

Way 1: the simple way

Walk from left to right and look for the drop: the first i where arr[i] < arr[i - 1]. If there is no drop, the array was not turned.

class Solution {
    public int findMinIndex(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i - 1]) return i;   // the drop: smallest is here
        }
        return 0;                                // never turned
    }
}

How long it takes: up to one look per box, O(n). Extra room: O(1).

Way 2: the clever way

Compare the middle box with the last box of the current range. The last box arr[hi] acts like a judge.

1. lo = 0, hi = n - 1.
2. While lo < hi, look at mid.
3. If arr[mid] > arr[hi], the numbers must drop somewhere after mid. The smallest is to the right: lo = mid + 1.
4. Otherwise arr[mid] <= arr[hi], so from mid to hi the numbers only climb. The smallest is mid or to its left: hi = mid. Keep mid in the range, it might be the answer.
5. When lo == hi, that is the index of the smallest.

class Solution {
    public int findMinIndex(int[] arr) {
        int lo = 0, hi = arr.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] > arr[hi]) lo = mid + 1;   // the drop is to the right of mid
            else hi = mid;                          // mid..hi climbs, smallest is mid or left
        }
        return lo;                                  // index of the smallest
    }

    public int findPivotIndex(int[] arr) {          // index of the biggest
        int m = findMinIndex(arr);
        return (m - 1 + arr.length) % arr.length;
    }
}

How long it takes: the range halves each time, O(log n). Extra room: O(1).

Watch out for

• Writing hi = mid - 1 in the "otherwise" case. mid itself might be the smallest, so keep it.
• Using while (lo <= hi) with hi = mid. When lo == hi the range never shrinks and the loop runs forever.
• Repeated numbers break the rule. With [3, 3, 1, 3], arr[mid] == arr[hi] tells you nothing. Then shrink with hi--, which is O(n) in the worst case.
• Know which answer is asked: the smallest's index (the rotation count) or the biggest's index (the pivot). They are next to each other.

What interviewers ask next

• How many times was the array rotated? It is the smallest's index.
• Search for a target in a rotated array. Find the smallest's index m, then binary search in [0, m - 1] or [m, n - 1], whichever can hold the target. Or do it in one pass by checking which half is sorted.
• With duplicates allowed (LeetCode 154)? When arr[mid] == arr[hi], do hi--. Worst case O(n), and no algorithm can do better in the worst case.
• Find the peak in a mountain array (goes up, then down)? A similar idea: compare arr[mid] with arr[mid + 1] and walk toward the higher side.

Remember this

Grown-up words: the turned array is a rotated sorted array, the jump is the rotation point, the biggest number is the pivot, and the smallest's index is the rotation count.