剑指Offer 图解 | 寻找旋转排序数组中的最小值

小鱼儿 2023-07-01 03:29 9阅读 0赞

点击上方蓝字设为星标![format_png][]

下面开始今天的学习～

![format_png 1][]

今天分享的题目来源于 LeetCode 上第 153 号问题：寻找旋转排序数组中的最小值。也是《剑指Offer》上的一道经典题。

### 题目描述 ###

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 **\[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)*，这时候 **二分查找法** 就浮现在脑海。

当然，这里是 **二分查找法** 的一种变体。

更多有关二分查找法的文章点击这篇：[一网打尽！二分查找解题模版与题型全面解析][Link 1]

二分的方法可以保证每次比较后，去掉数组中一半的元素。

这道题目中可以将 **中点** 与 **终点** 进行比较。

*  `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

![format_png 2][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9pY0hvZXJLTzNOakxHa0wzSmljWnh6WlVsTVBXYU9FVXRpYVZ5RHQ1QU9hSUpOa0xhbHRYT1lSaWFHU2J5aWJneFFzVkxSYXo5SnhmTjZLVkJtU05GYkZlNkx3LzY0MA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVFpYm1aNnRRaHBQU1ozYzhpYVB5cld2djdIY3pqNzl3NXY2Z3g1d0pkaWJvMFh5TUFOaWFGenpSQm5jVFVyOFBURWxWYTNiNHhubnN4WmliUS82NDA?x-oss-process=image/format,png
[Link 1]: https://blog.csdn.net/kexuanxiu1163/article/details/99619199
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVFpYm1aNnRRaHBQU1ozYzhpYVB5cld2djF6NFdoMjN0eUNSekJ6dFdmWWwwaWFWVTJDc0pzRkRpYUZrV01aUDEwb1owTTBBNFNCeWR0WkVnLzY0MA?x-oss-process=image/format,png