AlgoPressAppearance
0153-寻找旋转排序数组中的最小值
https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到： 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2] 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7] 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
提示：
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数 互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转
思路
暴力法直接查出最小的，但是不是面试官想要的结果
这个应该是二分法的衍生:
- 不管旋转多少次，最后也就是把数组从一半搬到另一半，或者没有搬动
- 二分之后，判断两边的分界线
设置左右边界和中间 left, right, mid
我们使用中间值 mid 做判断， 如果 nums[mid] < nums[right] 说明后半部分都是递增的，不在半部分， right = mid 继续 反之，如果 nums[mid] > nums[right] 说明在左半部分
1.为什么一个要+1 一个不需要-1 ？
可以这么理解：nums[mid]<nums[high]时，有可能nums[mid]本身就是最小值 然后mid-1就错过了mid 所以不要减1
2.那为什么mid可以加1？
可以这么理解：因为我们这题是求最小值，而nums[mid]>nums[high] 自然nums[mid]绝对不会是最小值，所以+1 过滤掉mid这个下标
参考代码
csharp
public class Solution {
public int FindMin(int[] nums) {
int left = 0;
int right = nums.Length - 1;
while(left < right){
int mid = left + (right - left ) / 2;
//如果中间值小于最大值，则最大值减小
//疑问：为什么 high = mid;而不是 high = mid-1;
//解答：{4,5,1,2,3}，如果high=mid-1，则丢失了最小值1
//这个时候其实就是考虑 mid 是不是有可能是答案，有可能的话 right = mid, 如果等于 mid - 1 的话有可能舍弃了答案
if(nums[mid] < nums[right]){
right = mid;
}
else{
//如果中间值大于最大值，则最小值变大
//疑问：为什么 low = mid+1;而不是 low = mid;
//解答：{4,5,6,1,2,3}，nums[mid]=6，low=mid+1,刚好nums[low]=1
//继续疑问：上边的解释太牵强了，难道没有可能low=mid+1,正好错过了最小值
//继续解答：不会错过!!! 如果nums[mid]是最小值的话，则其一定小于nums[high],走if，就不会走else了
left = mid + 1;
}
}
return nums[left];
}
}
另一种写法
csharp
public class Solution {
public int FindMin(int[] nums) {
int left = 0;
int right = nums.Length - 1;
while(left <= right){
int mid = left + (right - left ) / 2;
if(nums[mid] < nums[right]){
right = mid;
}
else{
left = mid + 1;
}
}
return nums[right];
}
}