Find Minimum in Rotated Sorted Array

Problem

You are given an array of length n which was originally sorted in ascending order. It has now been rotated between 1 and n times. For example, the array nums = [1,2,3,4,5,6] might become:

• [3,4,5,6,1,2] if it was rotated 4 times.
• [1,2,3,4,5,6] if it was rotated 6 times.

Notice that rotating the array 4 times moves the last four elements of the array to the beginning. Rotating the array 6 times produces the original array.

Assuming all elements in the rotated sorted array nums are unique, return the minimum element of this array.

A solution that runs in O(n) time is trivial, can you write an algorithm that runs in O(log n) time?

Examples

Example 1:

Input: nums = [3,4,5,6,1,2]

Output: 1

Example 2:

Input: nums = [4,5,0,1,2,3]

Output: 0

Example 3:

Input: nums = [4,5,6,7]

Output: 4

Constraints

• 1 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000

You should aim for a solution with O(logn) time and O(1) space, where n is the size of the input array.

Solution

Use the midpoint to check if its less than the right window. If so, that tells us the right side is monotonically increasing and the jump point must be on the left hand size.

class Solution {
public:
    int findMin(vector<int> &nums) {
        std::size_t l = 0;
        std::size_t r = nums.size() - 1;
        // Binary search
        // If middle < right, then its monotonically increasing on the right side,
        // and the jump (min element) must be on the left side
        while (l < r) {
            const auto m = std::midpoint(l, r);
            if (nums[m] < nums[r]) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return nums[l];
    }
};