154. Find Minimum in Rotated Sorted Array II Leetcode Java

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.

Solution:

All related problems:

33. Search in Rotated Sorted Array

81. Search in Rotated Sorted Array II 

153. Find Minimum in Rotated Sorted Array

154. Find Minimum in Rotated Sorted Array II

The duplicate number will cause that we can't determine which half is sorted when A[m]==A[r].

So for A[m]==A[r], we can't cut the array half, the only element we can exclude is A[r]. because even it is the minimum, we still have A[m](also the minimum) in the remaining array.

Duplication will degrade the time complexity to O(n)

      public int findMin(int[] num) {  
     if(num==null || num.length==0) return 0;  
     int l=0;  
     int r=num.length-1;  
     while(l<r){  
       int m=(r-l)/2+l;  
       if(num[m]<num[r]) r=m;  
       else if(num[m]>num[r]) l=m+1;  
       else r--;  
     }  
     return num[l];  
   }