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

小咪咪 2024-04-01 10:42 18阅读 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 次得到输入数组。

### 二分查找 ###

思路：**只要条件单调，二分就适用**  
旋转排序数组中的最小值，序列本身并不单调。  
但 <= 结尾这个条件，把序列分成两半，一半不满足(>结尾)，一半满足(<结尾)  
可以把“条件满足”看作1，不满足看作0，这就是一个 0/1 分段函数，二分查找分界点

二分代码三步走

1.  写二分条件 nums\[mid\] < nums\[结尾\]
2.  条件满足时，要right 还是要left
3.  另一半放入else中(left=mid+1,或right=mid-1)，  
    若是后者，mid=(left+right+1)  
    若题目有无解，上界+1，或下界-1，用于表示无解

class Solution {
        
        public int findMin(int[] nums) {
        
            /**
             *  所有元素比最后一个元素比较，大于则为0，小于则为1，
             * 就形成了个有序数组。
              */
            int left = 0;
            int right = nums.length-1;
            while (left<right){
        
                int mid = (left+right)/2;
                if(nums[mid]<nums[nums.length-1]){
        
                    right = mid;
                }else{
        
                    left = mid+1;
                }
            }
            return nums[right];
        }
    }

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

可参考[基本二分查找以及扩展][Link 1]

[7459c8fd341c42d09ecd3d466c0c57ea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/cdab8d3a343140c7b7b3d6d569c53dcf.png
[Link 1]: https://blog.csdn.net/ideaxx/article/details/127510796?spm=1001.2014.3001.5501