153. Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e.,0 1 2 4 5 6 7might become4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Solution:

1. Using binary search
   1. if mid < end, end = mid
   2. if mid > end, start = mid
2. Time complexity: O(logN)

 public int findMin(int[] nums) {
        if(nums == null)
            return 0;
        int min = nums[nums.length - 1];
        int start = 0;
        int end = nums.length - 1;
        int mid;
        while(start + 1 < end){
            mid = start + (end - start) / 2;
            if (nums[mid] < min){
                end = mid;
            }else{
                start = mid;
            }
        }
        if(nums[start] <= min){
            return nums[start];
        }else{
            return nums[end];
        }
    }

154. Find Minimum in Rotated Sorted Array II

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 7might become4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Solution:

If duplicates are allowed, may have mid == end, in this case, we cannot decide if we search from the left, or the right. In this case, we can only eliminate the end. We can still use binary search in this problem, but the worst case here will be O(n) as 101111111.

public int findMin(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }    

        int start = 0;
        int end = nums.length - 1;
        while(start + 1 < end){
            int mid = start + (end - start)/2;
            if(nums[mid] == nums[end]){
                end--;
            }else if(nums[mid] < nums[end]){
                end = mid;
            }else{
                start = mid;
            }
        }
        if(nums[start] <= nums[end]){
            return nums[start];
        }else{
            return nums[end];
        }

    }