153. Find Minimum in Rotated Sorted Array

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.

Q：给定一个由有序数组旋转（循环右移）后得到的数组，找出其中的最小元素。数组中无重复元素。要求时间复杂度O(logn)。

Constraints:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• All the integers of nums are unique.
• nums is sorted and rotated between 1 and n times.

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.

解决方法：二分查找

在有序的数组中使用二分查找可以实现O(logn)的时间复杂度。

• 数组旋转后可以认为其由两个有序数组构成，并且左侧有序数组的最小值（最左侧）一定严格大于右侧有序数组的最大值（在最右侧），严格大于是因为数组中无重复值。
• 整个数组中的最小值在右侧有序数组的最左侧。
• 左侧有序数组中的任何一个值都比右侧数组中的值大。
• 考虑使用二分查找在旋转数组中查找最小值：
  • 如果nums[mid]>nums[high]，那么nums[mid]肯定位于左侧有序数组中，而最小值肯定位于右半部分（不包括mid位置），执行low=mid+1;
  • 否则，也即nums[mid]<nums[high]，那么nums[mid]肯定位于右侧有序数组中，而最小值一定在mid的左侧（包括mid位置），执行high=mid;
  • 边界缩小后，[low:high]部分仍可以视作由一个有序数组旋转得到，仍然符合题意。
  • 边界条件，low=high，此时都指向最小值的位置。

    实现代码

    class Solution {
    public:
    int findMin(vector<int>& nums) {
       int low=0, high=nums.size()-1, mid=0;
       while(low < high){
           mid = (low+high)/2;
           if(nums[mid] < nums[high]){
               high = mid;
           }
           else{
               // nums[mid]>nums[high]
               low = mid + 1;
           }
       }
       return nums[low];
    }
    };

    运行效率评价

    Runtime: 3 ms, faster than 74.27% of C++ online submissions for Find Minimum in Rotated Sorted Array.
    Memory Usage: 10.1 MB, less than 72.86% of C++ online submissions for Find Minimum in Rotated Sorted Array.