[Binary Search] Find Minimum in Rotated Sorted Array

1. Example
Find the minimum element
No Duplicate exist in the array
s= [0 1 2 4 5 6 7]
s' = [4 5 6 7 0 1 2]

2. Implementation
Q1: Find minimum ?
A1: Binary search can do the job, why rotated sorted array?
Q1:
A1:
s=[4  5  6  7  0  1  2]
     0  1  2  3  4  5  6
l=0, r=6,m = (0+6)/2 = 3  
    7 >4 but 4 > 2   [l] < [m] && [l]  <  [r]
   l=m+1 = 4                r = m-1;
                             else
                                    l = m+1;
l=4, r=6, m =5
    5 > 0 but 0  < 2  [l] < [m] && [l] < [r]
  r = m-1=4                 r = m-1;
l=4, r=4                 else
                                  l=m+1;
                              [l] == [m]
  l ==r , return l

   
  r= m-1




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




Runtime Error Message:Line 113: java.lang.ArrayIndexOutOfBoundsException: -1
Last executed input:[1]
// NOTE:

int min = nums[0];

while ( l < r-1 ) 

else ( nums[l] > nums[m] ) 

 { 

 min = Math.min(nums[m], min); 

 r= m-1; 

 }

min = Math.min(nums[r], min); 

 min = Math.min(nums[l], min);

// Time:O(log(n)), Space:O(1)
public int findMin(int[] nums)
{
      
      
     // validate the input
     if ( nums==null || nums.length == 0 )
          return -1;


   

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


   

     int l = 0;
     int r = nums.length -1;


     int min = nums[0];



     while ( l < r-1 )
     {
          int m = (l+r) >>1;
          if ( nums[l] < nums[m] )
          {
               min = Math.min( nums[l], min);// for sorted side, we know leftmost is smallest and proceed comparison, and then search the other side
               l= m+1; 
          }
          else (  nums[l] > nums[m] ) 
          {
               min  = Math.min(nums[m], min);
               r= m-1;
          }
          else 
               l++;
     }



     min = Math.min(nums[r], min);
     min = Math.min(nums[l], min);
     return min;



}

}
public int findMin(int[] nums)
{
    return findMin(nums, 0, nums.legnth-1);
}
public int findMin(int[] nums, int left, int right)
{



    if (left == right)
       return nums[left];
    if ((right-left) ==1)
       return Math.min(nums[left], nums[right]);





    int m = left +(right-left)>>1;




    // not rotated
    if ( nums[right] > nums[left])
        return nums[left];
    else if (  nums[m] > nums[left] )
        return findMin(nums,m, right);
    else
        // [3,1,2] => [1]
        return findMin(nums, left, m);



}

// Time:O(log(n))
// *** The minimum element is the only element whose previous element is greater than it
public int findMin (int[] nums, int low, int high)
{


     // this condition is needed to handle the case when array is not rotated at all
     if (  high < low )
        return nums[0];
     // If there is only one element left
     if ( high == low)
        return nums[low];

     


     int mid = low+(hight-low)>>1;



     if ( mid < high && nums[mid+1] < nums[mid] )
        return nums[mid+1];

     if ( mid > low && nums[mid]  < nums[mid-1] )
        return nums[mid];





     if ( nums[high] > nums[mid] )
        return findMin(nums, low, mid-1);
     else 
        return findMin(nums, mid+1, high);
} 

3. Similar Ones
[Binary Search] Find Peak Element
[Binary Search] Search Insert Position
[Binary Search] Search for a Range
[Binary Search] Search for a 2D Matrix
[Binary Search] Search in Rotated Sorted Array