[M二分] lc153. 寻找旋转排序数组中的最小值(二分+边界情况+好题)

本文主要是介绍[M二分] lc153. 寻找旋转排序数组中的最小值(二分+边界情况+好题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 1. 题目来源
- 2. 题目解析

1. 题目来源

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

2. 题目解析

一道不错的二分题目。有两种写法，但两种写法的边界情况各不相同，需要考虑清楚。

思路：

数组中可能是完全升序的，也可能是前半段完全大于后半段的旋转的。
升序的很简单，只需要考虑 nums[0] < nums.back() 即可。
关注这个旋转的，可知，nums[0] 就是完全大于后半段的，同理 nums.back() 也是完全小于后半段的。
可以在 [l, r] 区间中取 mid，如果 nums[mid] > nums.back() 说明 mid 落在前半段，且 mid 不包含答案，则可以让 l = mid+1，否则，r = mid 即可。

上述方式使用 nums[mid]>nums.back() 进行判断的。如果写成 nums[mid] < nums[0] 实际上也能判断，此时应当让 r=mid，因为此时的 mid 落在右半段，且让 l=mid+1 即可。
但这样忽略了一个情况，即数组为升序的样例3 这个情况。所以可以通过特判去解决，主体代码仅考虑数组为旋转数组的情况。

这也提示我们一个技巧，可以通过一定的边界、情况的特判，将这些易出错的点特殊处理，再去考虑主体代码的实现。避免想太久。

针对一些整数二分的边界，需要将等号也要考虑清楚。

时间复杂度： $O(\log n)$
空间复杂度： $O (1)$

简洁写法：

class Solution {
public:int findMin(vector<int>& nums) {int n = nums.size();int l = 0, r = n - 1;while (l < r) {int mid = l + r >> 1;if (nums[mid] > nums.back()) l = mid + 1;else r = mid;}return nums[l];}
};

注意特判：

这里的特判还是蛮坑的。关于 mid 有下面的几种写法：

nums[mid] >= nums[0]
nums[mid] < nums[0]
nums[mid] > nums[0] 这个是无解的。因为此时 mid 其实位于第一段中，且隐藏着 nums[mid]==nums[0] 这个条件。理论上应该让 l = mid + 1。但是一开始 mid=0 的情况下，nums[mid]=nums[0] == nums[0]，就会走到 r = mid 这个逻辑里面去，但此时 r 不应该等于这个 nums[0] 这个非法值，它并不在答案所包含的区间内。
- 故，这个写法，找不到最小的起始点。
- 反而能找到最大的这个点。
- 反例， [2, 1]。一开始 nums[mid]=nums[0]=2，如果 r=mid 的话，则造成了错误的区间更新。此时 l=r=0，就有问题了。
nums[mid] <= nums[0]

class Solution {
public:int findMin(vector<int>& nums) {if (nums.back() > nums[0]) return nums[0];int l = 0, r = nums.size() - 1;while (l < r){int mid = l + r >> 1;// 这里的等号必须要加上。因为 nums[0] 不是一个可选答案// 不能将 r=mid 包含 nums[0]if (nums[mid] >= nums[0]) l = mid + 1;  else r = mid;}return nums[l];}
};