154. Find Minimum in Rotated Sorted Array II

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.

The array may contain duplicates.

Example 1:

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

Example 2:

Input: [2,2,2,0,1]
Output: 0

Note:

• This is a follow up problem to Find Minimum in Rotated Sorted Array.

• Would allow duplicates affect the run-time complexity? How and why?

Solution

class Solution {
    public int findMin(int[] nums) {
        int lo = 0;
        int hi = nums.length-1;
        int mid = 0;
        while(hi > lo){
            
            mid = lo + (hi - lo)/2;
            //find disorder sub list
            
            //it means the right side is disorder, privot must in this side
            if(nums[mid] > nums[hi]){
                lo = mid + 1;
            }
            //right side ordered, means left side disorder
            else if( nums[mid] < nums[hi]){
                hi = mid;
            }
            else{
                //means nums[mid] == nums[hi];
                //handle special case ex [0,1,1] or [1,1]
                hi--;
            }
            
        }
        return nums[lo];
    }
}