剑指Offer 图解 | 寻找旋转排序数组中的最小值
16lz
2021-01-22
题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0，1，2，4，5，6，7] 可能变为 [4，5，6，7，0，1，2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
输入: [3，4，5，1，2]
输出: 1
示例 2:
输入: [4，5，6，7，0，1，2]
输出: 0
题目解析
这道题目最简单粗暴的方式就是 直接遍历 整个数组来寻找，这个方法的时间复杂度为 O(N)，空间复杂度为 O(1) 。
不过，这样来做的话完全没有利用到题目给出一个条件 旋转 。
事实上，可以考虑将时间复杂度从 O(n) 缩小到 O(lgn)，这时候 二分查找法 就浮现在脑海。
当然，这里是 二分查找法 的一种变体。
更多有关二分查找法的文章点击这篇：一网打尽！二分查找解题模版与题型全面解析
二分的方法可以保证每次比较后，去掉数组中一半的元素。
这道题目中可以将 中点 与 终点 进行比较。
mid<end：最小值在左半部分。mid>end：最小值在右半部分。
也就是说只需要把 mid 和 end 比较，mid < end 丢弃右半部分（更新 end = mid），mid > end 丢弃左半部分（ 更新 start = mid + 1）。
直到 end 等于 start 时候结束就可以了。
补充：之所以这里 更新 start = mid + 1 而不是 start = mid 是因为存在一种特殊情况。当数组只剩两个元素的时候，mid = （start + end）/ 2，mid 取的就是 start。然后如果此时 mid > end，会发现 start 的位置不会变化，出现 死循环。（可以通过以下动画加深理解）
动画描述
代码实现
//author:程序员吴师兄
//source:图解面试算法
class Solution {
public int findMin(int[] nums) {
int low = 0, high = nums.length - 1;
while (low < high) {
if (nums[low] < nums[high]) return nums[low];
int mid = low + (high - low) / 2;
if (nums[mid] > nums[high]){
low = mid + 1;
} else{
high = mid;
}
}
return nums[low];
}
}
复杂度分析
时间复杂度：和二分搜索一样 O(logN)
空间复杂度：O(1)
相关题目推荐
LeetCode 33：搜索旋转排序数组
LeetCode 154：寻找旋转排序数组中的最小值 II
更多相关文章
- 视频讲解 | 图解剑指offer：二维数组的查找
- 超详细！详解一道高频算法题：数组中的第 K 个最大元素
- 图解 LeetCode 第 421 题：数组中两个数的最大异或值
- 一道简单的数组遍历题，加上四个条件后感觉无从下手
- 数组特性的妙用！如何找到「缺失的第一个正数」
- 图解「剑指Offer」之旋转数组的最小数字
- 图解「剑指Offer」之二维数组中的查找
- 动画：面试必刷之找出数组中重复的数字
- 动画：面试必刷之二维数组中查找一个元素