Find the Minimum in a Sorted and Rotated Array

A sorted array of distinct integers was rotated at an unknown pivot: [0, 1, 2, 4, 5, 6, 7] might have become [4, 5, 6, 7, 0, 1, 2]. Find the minimum element in O(log n).

LeetCode: 153. Find Minimum in Rotated Sorted Array

Example

Text

Input:  [4, 5, 6, 7, 0, 1, 2]    Output: 0
Input:  [3, 4, 5, 1, 2]          Output: 1
Input:  [11, 13, 15, 17]         Output: 11   (rotated by 0)

Brute force: linear scan

Java

public class Main {
    static int findMin(int[] nums) {
        int min = nums[0];
        for (int x : nums) {
            min = Math.min(min, x);
        }
        return min;
    }

    public static void main(String[] args) {
        System.out.println(findMin(new int[] {4, 5, 6, 7, 0, 1, 2}) + " " + findMin(new int[] {3, 4, 5, 1, 2}) + " " + findMin(new int[] {11, 13, 15, 17}));
    }
}

Output

0 1 11

Time: O(n). Space: O(1).

Optimal: binary search against the right end

The array is two sorted runs, and the minimum is the first element of the second run. Compare the middle element with the last element of the current range:

nums[mid] > nums[hi]: mid is in the first (larger) run, so the minimum is to the right of mid.
Otherwise mid is in the second run, so the minimum is at mid or to its left.

Java

public class Main {
    static int findMin(int[] nums) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] > nums[hi]) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return nums[lo];
    }

    public static void main(String[] args) {
        System.out.println(findMin(new int[] {4, 5, 6, 7, 0, 1, 2}) + " " + findMin(new int[] {3, 4, 5, 1, 2}) + " " + findMin(new int[] {11, 13, 15, 17}));
        System.out.println(findMin(new int[] {2, 1}) + " " + findMin(new int[] {5}));
    }
}

Output

0 1 11
1 5

Time: O(log n). Space: O(1).

Comparing with nums[hi] rather than nums[lo] is what makes an unrotated array work: every nums[mid] <= nums[hi], so hi moves left until it reaches index 0. The final lo is also the rotation count.

Edge cases

Not rotated: returns nums[0].
Two elements: [2, 1] gives 1.
Duplicates (LeetCode 154): when nums[mid] == nums[hi], it is unknown which side the minimum is on. Drop one element with hi -= 1, which is safe because nums[mid] has the same value. The worst case becomes O(n).