153. 寻找旋转排序数组中的最小值

╰+哭是因爲堅強的太久メ 2023-10-11 17:12 31阅读 0赞

## 题目描述： ##

> 已知一个长度为 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 次得到输入数组。

题目说了一堆，意思就是一个数组分两部分，每一部分都是有序的，通过两个部分相连接的地方就是最小值，然后让你找到这个最小值。  
题目中让写一个log n的算法，表面是一个限制，其实就是在告诉我们一个思路：使用二分法  
我们知道有序的序列使用二分法效率很高很方便，可是这个是分成两部分有序，那怎么办？  
我们分成两个部分：  
在二分查找的每一步中，左边为left,右边为right，中间值为mid

*  如果nums\[mid\]<nums\[right\]，则说明最小值一定在mid以及mid左边，此时我们 可以让游标right移动到mid的位置；  
    ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAWk5pbmVTdW4_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]
 *  如果nums\[mid\]>nums\[right\]，则说明最小值一定在mid的右边，那么我们就可以让游标left移动到mid+1的位置；  
    ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAWk5pbmVTdW4_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]

按照这个思路，具体实现就非常简单了

public class 寻找旋转排序数组中的最小值_153 {
        
        public int findMin(int[] nums) {
        
            int low = 0;
            int high = nums.length - 1;
            while (low < high) {
        
                int pivot = (low + high) / 2;
                if (nums[pivot] < nums[high]) {
        //说明最小值一定在mid以及mid左边
                    high = pivot;
                } else {
        //说明最小值一定在Mid右边
                    low = pivot + 1;
                }
            }
            return nums[low];
    
        }
    
        public static void main(String[] args) {
        
            寻找旋转排序数组中的最小值_153 test = new 寻找旋转排序数组中的最小值_153();
            System.out.println(test.findMin(new int[]{
        4, 5, 6, 7, 0, 1, 2}));
    
        }
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAWk5pbmVTdW4_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: https://img-blog.csdnimg.cn/b37e918e400a492ab904ead67335afce.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAWk5pbmVTdW4=,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAWk5pbmVTdW4_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]: https://img-blog.csdnimg.cn/faa0dcf4415c4a34bfabf8ebedc385e9.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAWk5pbmVTdW4=,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center