153. Find Minimum in Rotated Sorted Array Leetcode Java

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.

You may assume no duplicate exists in the array.

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
It is very similar to previous rotated sorted array problem. If there is no duplicated element in the array, according to the relationship between A[mid] and A[r], we can determine whether the left half is sorted or the right half is sorted. With this information we can cut the unnecessary half and find the minimum element. 

two cases:

 1.if right half is sorted, the minimum must between l and m(inclusive)

 2. if left half is sorted(right half is not sorted), the minimum must between m+1 and r(inclusive). 

Must compare with right and first determine if right half is sorted to avoid the corner case that the array is complete sorted. So eg. if left half is sorted and right half is sorted as well, we can't say the minimum is in the right half. It is very important that right half is not sorted for the second case.
Time complexity: O(logn)

   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]){ //right half is sorted  
        r=m;  
      }  
      else l=m+1;  
    }  
    return num[l];  
   }