package com.fishercoder.solutions;

/**
 * 154. Find Minimum in Rotated Sorted Array II

 Suppose an array sorted in ascending order 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.

 Example 1:
 Input: [1,3,5]
 Output: 1

 Example 2:
 Input: [2,2,2,0,1]
 Output: 0

 Note:
 This is a follow up problem to Find Minimum in Rotated Sorted Array.
 Would allow duplicates affect the run-time complexity? How and why?

 */
public class _154 {
  public static class Solution1 {
    public int findMin(int[] nums) {
      int left = 0;
      int right = nums.length - 1;
      if (nums[left] < nums[right]) {
        return nums[left];
      }
      int min = nums[0];
      while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        min = Math.min(min, nums[mid]);
        if (nums[mid] > nums[left]) {
          min = Math.min(nums[left], min);
          left = mid + 1;
        } else if (nums[mid] < nums[left]) {
          right = mid - 1;
        } else {
          left++;
        }
      }
      min = Math.min(min, Math.min(nums[left], nums[right]));
      return min;
    }
  }
}

@@ -33,515 +33,8 @@
 s;%0A%0A
-/**%0A * 154. Find Minimum in Rotated Sorted Array II%0A%0A Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.%0A%0A (i.e.,  %5B0,1,2,4,5,6,7%5D might become  %5B4,5,6,7,0,1,2%5D).%0A%0A Find the minimum element.%0A%0A The array may contain duplicates.%0A%0A Example 1:%0A Input: %5B1,3,5%5D%0A Output: 1%0A%0A Example 2:%0A Input: %5B2,2,2,0,1%5D%0A Output: 0%0A%0A Note:%0A This is a follow up problem to Find Minimum in Rotated Sorted Array.%0A Would allow duplicates affect the run-time complexity? How and why?%0A%0A */%0A
 publ
@@ -49,16 +49,18 @@
  _154 %7B%0A
+  
   public
@@ -85,16 +85,20 @@
 tion1 %7B%0A
+    
     publ
@@ -122,24 +122,30 @@
 t%5B%5D nums) %7B%0A
+      
       int le
@@ -154,24 +154,30 @@
  = 0;%0A      
+    
+  
 int right = 
@@ -195,24 +195,30 @@
  - 1;%0A      
+    
+  
 if (nums%5Blef
@@ -241,24 +241,32 @@
 ) %7B%0A        
+   
+     
 return nums%5B
@@ -274,26 +274,38 @@
 eft%5D;%0A      
+     
+ 
 %7D%0A
+      
       int mi
@@ -323,16 +323,22 @@
 ;%0A      
+    
+  
 while (l
@@ -352,24 +352,32 @@
  %3C right) %7B%0A
+        
         int 
@@ -409,16 +409,24 @@
 t) / 2;%0A
+        
         
@@ -457,32 +457,40 @@
 %5Bmid%5D);%0A        
+   
+     
 if (nums%5Bmid%5D %3E 
@@ -505,32 +505,42 @@
 t%5D) %7B%0A          
+     
+     
 min = Math.min(n
@@ -556,16 +556,26 @@
 , min);%0A
+          
         
@@ -596,24 +596,32 @@
  1;%0A        
+      
+  
 %7D else if (n
@@ -655,16 +655,26 @@
         
+         
+ 
 right = 
@@ -678,24 +678,32 @@
  = mid - 1;%0A
+        
         %7D el
@@ -713,24 +713,34 @@
 %7B%0A          
+ 
+         
 left++;%0A    
@@ -747,18 +747,18 @@
     
+  
-%7D%0A
       %7D%0A
     
@@ -749,24 +749,44 @@
           %7D%0A
+            %7D%0A      
       min = 
@@ -835,16 +835,22 @@
 ght%5D));%0A
+      
       re
@@ -863,16 +863,22 @@
 in;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 154