LC153.寻找旋转排序数组中的最小值

原题链接
image.png

思路：二分查找

  • 此题的二分性体现在“最小值不可能在哪一侧，就把哪一侧放弃掉”
  • 原题里面数组旋转过很多次了，但是无论怎么旋转，本质上都是两段

image.png

  • 最小值一定出现在无序的一侧，如果nums[mid] < nums[right]，那右侧一定有序，反之左侧一定有序。

    代码：

    1. class Solution {LC33.
    2. public:
    3.   int findMin(vector<int>& nums) {
    5.       // 二段性：最小值不可能在哪一侧
    6.       int n = nums.size();
    7.       int left = 0, right = n - 1;
    8.       while (left < right) {
    9.           int mid = (left + right) / 2;
    10.           // 只要nums[right] > nums[mid] 
    11.           // 右边一定需要放弃掉
    12.           if (nums[right] > nums[mid]) {
    13.               right = mid;
    14.           } else {
    15.               left = mid + 1;
    16.           }
    17.       }
    19.       return nums[left];
    20.   }
    21. };