LeetCode_二分搜索_中等_153.寻找旋转排序数组中的最小值

àì夳堔傛蜴生んèń 2023-10-06 23:17 2阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

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

**提示：**  
n == nums.length  
1 <= n <= 5000  
\-5000 <= nums\[i\] <= 5000  
nums 中的所有整数互不相同  
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array

## 2.思路 ##

（1）二分搜索  
思路参考[本题官方题解][Link 1]。

具体思路如下：在遍历数组 nums 的过程中：将数组的第一个和最后一个元素进行比较，如果第一个元素小于最后一个元素，则数组是升序的，因此最小元素是数组的第一个元素。否则，使用二分搜索将数组分成两个子数组，并查看哪个子数组包含最小元素。该算法的基本思想是找到具有下列性质的位置 mid：

nums[mid] < nums[mid + 1] && nums[mid] < nums[mid - 1]

这表明 mid 是最小元素的所在的下标位置。

相关题目：  
[LeetCode\_二分搜索\_中等\_33.搜索旋转排序数组][LeetCode_33.]  
[LeetCode\_二分搜索\_中等\_81.搜索旋转排序数组 II][LeetCode_81._ II]  
[LeetCode\_二分搜索\_困难\_154.寻找旋转排序数组中的最小值 II][LeetCode_154._ II]

## 3.代码实现（Java） ##

//思路1————二分搜索
    class Solution {
        
        public static int findMin(int[] nums) {
        
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) {
        
            	//如果 nums[left] < nums[right]，则说明 nums[left...right] 之间的元素是升序的，所以最小元素就是 nums[left]
                if (nums[left] < nums[right]) {
        
                    return nums[left];
                }
                int mid = left + (right - left) / 2;
                if (nums[mid] < nums[right]) {
        
                	//如果 nums[mid] < nums[right]，说明最小值在 mid 左侧或者就是 mid 本身
                    right = mid;
                } else {
        
                	//如果 nums[mid] >= nums[right]，说明最小值在 mid 右侧
                    left = mid + 1;
                }
            }
            return nums[right];
        }
    }

[Link 1]: https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/solution/xun-zhao-xuan-zhuan-pai-xu-shu-zu-zhong-5irwp/
[LeetCode_33.]: https://blog.csdn.net/weixin_43004044/article/details/118211776
[LeetCode_81._ II]: https://blog.csdn.net/weixin_43004044/article/details/120010758
[LeetCode_154._ II]: https://blog.csdn.net/weixin_43004044/article/details/129377572