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

153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

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

这个题目事实上比 33. 搜索旋转排序数组是更好写的，是比较纯粹的二分。最好通过画图来理解为什么每次去跟 nums[R] 比较——这和旋转排序数组「分段单调递增」的特性是有关系的。

二刷

class Solution {
public:
  int findMin(vector<int>& nums) {
    int Min = INT_MAX;
    int L = 0, R = nums.size();
    while (L != R) {
      int M = L + (R - L) / 2;
      Min = std::min(Min, std::min(nums[L], nums[M]));
      if (nums[L] < nums[M])
        L = M + 1;
      else
        R = M;
    }
    return Min;
  }
};

这个问题似乎非常特殊——官解采用的是闭区间写法，我用的是半开半闭。但是官解用闭区间的原因是它要在每一步里和 nums[R] 作比较，实际上我这个写法是行不通的，所以一时半会没想到具体该怎么写。

后来我问了下 Gemini，它给我解释得很清楚：其实压根没必要跟 nums[R] 去比较，直接跟 nums.right() 比较就可以了，因为整个数组的最小元素，只能是右区间的最左边元素。

class Solution {
public:
  int findMin(vector<int>& nums) {
    int L = 0, R = nums.size();
    while (L != R) {
      int M = L + (R - L) / 2;
      // If M is greater than the last element, it's in the left half.
	  // The minimum must be strictly to its right.
      if (nums[M] > nums.back())
        L = M + 1;
      // If M is less than or equal to the last element, it's in the right half.
      // M could be the minimum, so it becomes our new exclusive upper bound
      // for the search of the FIRST valid element.
      else
        R = M;
    }
    return nums[L];
  }
};

所以说这个问题就转化成了「找到第一个比 nums.right() 小的元素」。我们采用的策略就是：先跑到右区间去，然后在右区间当中，慢慢收窄右指针的值，直到最后收窄到 L == R，退出返回。

注意 Gemini 给我加的那两句注释。这个方法事实上也用到了「右区间元素严格小于左区间」的特性，同时也利用到了求 M 时向下取整的特性——这使得在循环体中有严序 \(LM 在区间逐步收窄的过程当中可以指向最小元素。说实话这个解法还是挺神的。

三刷

class Solution {
public:
  int findMin(vector<int>& nums) {
    int L = 0, R = nums.size();
    while (L != R) {
      int M = L + (R - L) / 2;
      // Is this bound to the nature of flooring?
      if (nums.back() < nums[M])
        L = M + 1;
      else
        R = M;
    }
    return nums[L];
  }
};

确实跟向下取整有关系。看看二刷我写的那个题解。