LeetCode153. 寻找旋转排序数组中的最小值【二分查找】

电玩女神 2022-11-17 03:50 188阅读 0赞

难度：`中等`  
题目描述：

> 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转 后，得到输入数组。  
> 例如，原数组 nums =\[0,1,2,4,5,6,7\] 在变化后可能得到：  
> 若旋转 4 次，则可以得到 \[4,5,6,7,0,1,2\]  
> 若旋转 4 次，则可以得到 \[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它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]: /images/20221022/cdd990d26a9f4c0da48d2b84da87ce32.png