java算法：154. 寻找旋转排序数组中的最小值 II

题目

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：

若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]

若旋转 7 次，则可以得到 [0,1,4,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 ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

用二分查找的思路：

定义2个指针：l，r，分别指向左右两边；

定义一个函数，getMin(nums,l,r）,这个函数的功能是找到数组中l到r中的最小值；

在这个函数中，有一个中间指针mid = (l+r)/2；

如果num[mid]>=num[l];说明左边是有序的，nums[l]是左边的最小值；右边的最小值还无法确定[mid+1,r]

否则，说明右边是有序的，nums[mid]是右边的最小值；左边还无法确定[l,mid-1]

然后递归这函数并返回左右两边的最小值：math.min(min,getMin(nums,l,r));

代码

public static int findMin(int[] nums) {
        int length = nums.length;
        if (length == 0) return 0;
        if (length == 1) return nums[0];
        int l = 0,r = length-1;
        int min = getMin(nums,l,r);

        return min;

    }

    private static int getMin(int[] nums, int l, int r) {
        if (r-l<2) {
            return Math.min(nums[l],nums[r]);
        }
        int mid = (l+r)/2;
        int min = nums[l];
        if (nums[l] == nums[mid] && nums[mid] == nums[r]){
            l++;
            r--;
            return getMin(nums,l,r);
        }
        if (nums[l]<=nums[mid]){
            min = nums[l];
            l=mid+1;

        }else {
            min = nums[mid];
            r=mid-1;
     }
        return Math.min(min,getMin(nums,l,r));
    }
           

官方答案分析：

旋转数组类似于这种双曲线

我们找到他的中点：mid = (l +r)/2;

用中点的值去跟右边的值相比较，nums[r],nums[mid] 有三种情况:

• num[mid] < num [r] :说明最小值一定在[l,mid] 区间上。r = mid；
• num[mid] > num[r] :说明最小值一定在 [rmid+1,r] 区间上。l = mid+1；

• num[mid] = num[r] : 因为可能重复产生的特殊情况，最小值一定在 [ l, r-1] 上。r–；

  就这样循环的折半查找，直到 l>=r时，最小值一定是 num[l].

  具体代码:

public static int findMin(int[] nums) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        while(left<right){
            int mid = (left + right)/2;
            if(nums[mid]<nums[right]){
                right = mid;
            }else if( nums[mid]>nums[right]){
                left = mid + 1;
            }else{
                right--;
            }
        }
        return nums[left];
    }