首页 > 代码库 > Find Minimum in Rotated Sorted Array II 旋转数组中找最小值(有重复元素) @LeetCode

Find Minimum in Rotated Sorted Array II 旋转数组中找最小值(有重复元素) @LeetCode

递归


public class Solution {
    public int findMin(int[] num) {
        return helper(num, 0, num.length-1);
    }
    
    //with duplicate
    public static int helper(int[] a, int left, int right){
         
        //one element
        if(left == right){
            return a[left];
        }
         
        //two elements
        if(left == right-1){
            return a[left]<a[right]? a[left]: a[right];
        }
         
        //the array is ordered
        if(a[left] < a[right]){
            return a[left];
        }
         
        int mid = (left+right)/2;
         
        if(a[mid] > a[left]){
            return helper(a, mid, right);
        }else if(a[mid] < a[left]){
            return helper(a, left, mid);
        }else{ //when a[mid] == a[left], we have to search both side
            return Math.min(helper(a, mid, right), helper(a, left, mid));
        }
         
    }
}





Find Minimum in Rotated Sorted Array II 旋转数组中找最小值(有重复元素) @LeetCode