Wednesday, December 31, 2014

Leetcode 154: Find Minimum in Rotated Sorted Array II


Problem:

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.

Analysis:

Based on the previous analysis of Leetcode 154, we just need to specify the action if mid equals
to the left.
Leetcode 154: Find Minimum in Rotated Sorted Array

Code:

public class Solution {
   public int findMin(int[] num) {
       int left=0;
       int right=num.length-1;
       int min=Integer.MAX_VALUE;
       while(left<=right){
           int mid=(left+right)/2;
           min=Math.min(min,num[mid]);
           if(num[left]<num[mid]){ //A[left..mid] is sorted
               min=Math.min(min,num[left]);
               left=mid+1;
           }else if(num[left]>num[mid]){ //A[mid..right] is sorted
               right=mid-1;
           }else{
               left++;
           }
       }
       return min;
   }
}

No comments:

Post a Comment