大家好呀，我是帅蛋。
今天解决寻找旋转排序数组中的最小值，这是二分查找的最后一道实战题。
真是最后一道，大家忍一下。
其实本来还有几道二分查找的题准备写的，但是看着大家对二分查找的兴趣好像不是很大，当然也可能是觉得太简单...
我也不准备写了...
话不多说，让我们快点完事。
LeetCode 153：寻找旋转排序数组中的最小值
题意
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。
例如：nums = [0,1,2,4,5,6,7] 旋转 4 次可以得到 [4,5,6,7,0,1,2]。
给你一个无重复元素的数组 nums，原来是一个升序数组，并按照上述情形做了多次旋转。
请你找出并返回数组中的最小元素。
示例
输入：[4,5,6,7,0,1,2]
输出：1
解释：原数组为 [0,1,2,4,5,6,7]，旋转 4 次得到输入数组。
提示
注意数组 [a[0],a[1],a[2],...,a[n-1]] 旋转一次的结果为数组 [a[n-1],a[0],a[1],...,a[n-2]]。
- 1 <= n == len(nums) <= 5000
- -5000 <= nums[i] <= 5000
- nums 中的所有整数互不相同
- nums 原先是一个升序数组，并进行了 1 ~ n 次旋转
题目解析
难度中等，值得一搞。
其实关于旋转排序数组，我们已经做过两种类型的了：
Ⅰ是数组 nums 无重复元素，Ⅱ是数组 nums 存在重复元素。
本题旋转排序数组和 Ⅰ 是一种类型，数组 nums 无重复元素。
但是本题又有不同，之前的题是给出一个 target，在 nums 中找是否存在 target，而本题是直接在旋转数组中找最小值。
题虽不同，但是做法没有大的改变，无非就是维护一个最小值的指针，每次比较就更新当前的最小值。
如果你吃透了前面两道旋转排序数组，这道题对你来说，应该是简单题。
具体步骤如下：
- 初始化一个最小值指针 nums_min。
- 找出 mid，如果 nums[mid] < nums_min，更新 nums_min。
- 如果左半区有序，维护 nums_min，范围缩小至[mid+1,high]。
- 否则就找右半区，维护 nums_min，范围缩小至[low,mid-1]。
图解
以 [4,5,6,7,0,1,2] 为例。
首先初始化 low，high 及 nums_min 指针。
low, high = 0, len(nums) - 1 nums_min = float('inf')
第 1 步，low = 0，high = 6，mid = low + (high - low) // 2 = 3：
mid = low + (high - low) // 2
此时 nums_min = inf， nums[mid] < nums_min，所以维护最小值指针 nums_min 的值。
if nums[mid] < nums_min: nums_min = nums[mid]
当前 nums[low] < nums[mid]，证明左区间有序。
nums_min > nums[low]，维护最小值指针 nums_min，同时 low 向右移动至 mid + 1 处。
if nums[low] < nums[mid]: if nums_min > nums[low]: nums_min = nums[low] low = mid + 1
第 2 步，low = 4，high = 6，mid = low + (high - low) // 2 = 5：
此时 nums_min = 4， nums[mid] < nums_min，所以维护最小值指针 nums_min 的值。
当前 nums[low] < nums[mid]，证明左区间有序。
nums_min > nums[low]，维护最小值指针 nums_min，同时 low 向右移动至 mid + 1 处。
第 3 步，low = 6，high = 6，mid = low + (high - low) // 2 = 6：
此时 nums_min = 0， nums[mid] > nums_min。
并且 nums[low] >= nums[mid]，证明右区间有序，nums_min < nums[high]，high 指针向右移动至 mid - 1。
此时，high < low，循环结束，返回最小值 nums_min。
本题解使用二分查找，所以时间复杂度为 O(logn)。
只是额外的维护了几个指针，所以空间复杂度为 O(1)。
代码实现
Python 代码实现
class Solution: def findMin(self, nums: List[int]) -> int: if len(nums) == 1: return nums[0] low, high = 0, len(nums) - 1 nums_min = float('inf') while low <= high: mid = low + (high - low) // 2 if nums[mid] < nums_min: nums_min = nums[mid] if nums[low] < nums[mid]: if nums_min > nums[low]: nums_min = nums[low] low = mid + 1 else: if nums_min > nums[high]: nums_min = nums[high] high = mid - 1 return nums_min
Java 代码实现
class Solution { public int findMin(int[] nums) { if(nums.length == 1){ return nums[0]; } int low = 0; int high = nums.length - 1; int nums_min = 5001; while (low <= high){ int mid = low + (high - low) / 2; if(nums[mid] < nums_min){ nums_min = nums[mid]; } if(nums[low] < nums[mid]){ if(nums_min > nums[low]){ nums_min = nums[low]; } low = mid + 1; }else{ if(nums_min > nums[high]){ nums_min = nums[high]; } high = mid - 1; } } return nums_min; } }
图解寻找旋转排序数组中的最小值到这就结束辣，这也意味着现阶段的二分查找到这就结束了。
如果是认真跟下来的小宝贝肯定是收获满满，这点我还是很自信的。
还是那句话，总体来说呢，二分查找就是个事儿精，细节控，在用二分的时候一定要打起十二分精神。
下面我们来开始新的专题，如果期待的话，记得给我三连：点赞 + 在看 + 转发。
让我看到你！
我是帅蛋，我们下次见
