【算法|二分查找No.6】leetcode 153. 寻找旋转排序数组中的最小值

àì夳堔傛蜴生んèń 2024-04-27 07:01 52阅读 0赞

> 个人主页：[兜里有颗棉花糖][Link 1]  
> 欢迎 点赞? 收藏✨ 留言✉ 加关注?本文由 [兜里有颗棉花糖][Link 1] 原创  
> 收录于专栏【[手撕算法系列专栏][Link 2]】【[LeetCode][]】  
> ?本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助  
> ?希望我们一起努力、成长，共同进步。

**原题链接：[点击直接跳转到该题目][Link 3]**

#### 目录 ####

*  1️⃣题目描述
 *  2️⃣代码编写

## 1️⃣题目描述 ##

已知一个长度为 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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

**示例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 次得到输入数组。

![在这里插入图片描述][b2dea308bec1407dbd565eb143f76c0b.png]

## 2️⃣代码编写 ##

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

**最后就顺利通过啦！！！**

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[Link 2]: https://blog.csdn.net/m0_74352571/category_12364106.html
[LeetCode]: https://blog.csdn.net/m0_74352571/category_12252087.html
[Link 3]: https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/
[b2dea308bec1407dbd565eb143f76c0b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/7ae4d213c42e4a6dbe110de935c4b6bf.png