Follow up for "Find Minimum in Rotated Sorted Array":

What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

 

Suppose a sorted array 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.

The array may contain duplicates.

// [小][大] ->(rotate)-> [大][小]，只有在pivot处才会有逆序public class Solution {    public int findMin(int[] nums) {                int result = Integer.MAX_VALUE;        int left = 0;        int right = nums.length - 1;                while(left <= right){            int middle = (left + right) / 2;                        if(nums[middle] < nums[right]){          //m-r段有序                if(nums[middle] < result){                    result = nums[middle];                }                right = middle - 1;            }else if(nums[middle] > nums[right]){    //l-m段有序                if(nums[left] < result){                    result = nums[left];                }                left = middle + 1;            }else{                                   //不能判断，移动边缘                if(nums[right] < result){                    result = nums[right];                }                right--;            }        }                return result;    }}