在翻转的有序数组中查找最小值

Problem

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array

nums = [0,1,2,4,5,6,7]

might become:

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

Notice that rotating an array

[a[0], a[1], a[2], ..., a[n-1]]

1 time results in the array

[a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2] Output: 0 Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17] Output: 11 Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Idea

Use binary search.

Compare the middle element with the rightmost element. If the middle element is greater than the rightmost element, the minimum must be in the right half, so move the left pointer to mid + 1.

If the middle element is smaller than the rightmost element, the minimum is either the middle element itself or somewhere to its left, so move the right pointer to mid.

Keep doing this until left and right point to the same position. That position contains the minimum.

Time complexity: \(O(\log n)\), Space complexity: \(O(1)\)

Pseudo-code

while (left < right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] < nums[right]) {
        right = mid;
    } 
    else {
        left = mid + 1;
    }
}
return nums[left];