153. Find Minimum in Rotated Sorted Array 寻找旋转有序数组的最小值

[GH1995]

153. Find Minimum in Rotated Sorted Array

Difficulty: Medium

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

Input: [3,4,5,1,2] 
Output: 1

Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0

Solution

Language: C++

class Solution {
 public:
  int findMin(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    // 比较第一个和最后一个数的大小，如果第一个数小，则没有旋转，如果第一个数大，就要进一步搜索
    if (nums[left] > nums[right]) {
      while (left != right - 1) {
        // left指的数比较，如果中间的数大，则继续二分查找右半段数组，反之查找左半段
        auto mid = (left + right) / 2;
​
        if (nums[left] < nums[mid]) {
          left = mid;
        } else {
          right = mid;
        }
      }
      return min(nums[left], nums[right]);
    } else {
      return nums[0];
    }
  }
};

[GH1995]

比较第一个和最后一个数的大小，如果第一个数小，则没有旋转

---

left指的数比较，如果中间的数大，则继续二分查找右半段数组，反之查找左半段