LeetCode.153.Find Minimum in Rotated Sorted Array 旋转排序数组中的最小值

题目描述

153 Find Minimum in Rotated Sorted Array
https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
You may assume no duplicate exists in the array.

Example 1:

Input: [3,4,5,1,2]
Output: 1

Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0

---

相似题目

LeetCode.033.Search in Rotated Sorted Array 搜索旋转排序数组
LeetCode.153.Find Minimum in Rotated Sorted Array 旋转排序数组中的最小值

---

解题过程

找旋转有序数组的最小值，二分搜索。用mid和low，high比较，判断转折点也就是极值点的位置：
当 a[low,…,high] 是旋转升序数组时（完全有序不考虑），并且也没有重复值时：
如果 a[mid]>a[low]，说明左边升序，转折点在右边，最小值也在右边，也可以用 a[mid]>a[high] 判断
如果 a[mid]<a[low]，说明右边升序，转折点在左边，最小值也在左边，也可以用 a[mid]<a[high] 判断

思想很好理解，但里面有坑，很容易出错。当a是{2,1}这种只有2个值且倒序的数组，这时a[low]==a[mid]，很容易出错，我改了好几遍才写对。

SolutionV2018

private static class SolutionV2018 {
    public int findMin(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) {
            //先判断nums[low,...,high]是否升序，即无旋转
            if (nums[low] <= nums[high]) {
                return nums[low];
            }
            //nums[low,...,high]不是升序
            int mid = (low + high) / 2;
            if (nums[mid] >= nums[low]) {//左边升序，转折点在右边，最小值也在右边
                low = mid + 1;
            } else {//右边升序，转折点在左边，最小值也在左边
                high = mid;
            }
        }
        return nums[low];
    }
}

SolutionV2020

第二遍写，竟然写的更复杂了

private static class SolutionV2020 {
    public int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            if (low == high) {
                return nums[low];
            }
            if (high == low + 1) {
                return Math.min(nums[low], nums[high]);
            }
            int mid = (low + high) / 2;
            if (nums[mid] < nums[mid - 1]) {
                return nums[mid];
            }
            if (nums[low] <= nums[mid] && nums[mid] <= nums[high]) {
                // 左右都有序
                return nums[low];
            } else if (nums[low] <= nums[mid]) {
                // 左边是有序的，最小值肯定再右边
                low = mid + 1;
            } else {
                // 右边是有序的，最小值肯定在左边
                high = mid - 1;
            }
        }
        return nums[low];
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_153_FindMinimumInRotatedSortedArray.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_153_FindMinimumInRotatedSortedArray.java

---