package com.fishercoder.solutions;

/**
 * 81. Search in Rotated Sorted Array II
 *
 * Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
 *
 * (i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
 *
 * You are given a target value to search. If found in the array return true, otherwise return false.
 *
 * Example 1:
 *
 * Input: nums = [2,5,6,0,0,1,2], target = 0
 * Output: true
 * Example 2:
 *
 * Input: nums = [2,5,6,0,0,1,2], target = 3
 * Output: false
 * Follow up:
 *
 * This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
 * Would this affect the run-time complexity? How and why?
 */
public class _81 {

  public static class Solution1 {
    public boolean search(int[] nums, int target) {
      int start = 0;
      int end = nums.length - 1;

      //check each num so we will check start == end
      //We always get a sorted part and a half part
      //we can check sorted part to decide where to go next
      while (start <= end) {
        int mid = start + (end - start) / 2;
        if (nums[mid] == target) {
          return true;
        }

        //if left part is sorted
        if (nums[start] < nums[mid]) {
          if (target < nums[start] || target > nums[mid]) {
            //target is in rotated part
            start = mid + 1;
          } else {
            end = mid - 1;
          }
        } else if (nums[start] > nums[mid]) {
          //right part is rotated

          //target is in rotated part
          if (target < nums[mid] || target > nums[end]) {
            end = mid - 1;
          } else {
            start = mid + 1;
          }
        } else {
          //duplicates, we know nums[mid] != target, so nums[start] != target
          //based on current information, we can only move left pointer to skip one cell
          //thus in the worst case, we would have target: 2, and array like 11111111, then
          //the running time would be O(n)
          start++;
        }
      }
      return false;
    }
  }
}

@@ -33,660 +33,8 @@
 s;%0A%0A
-/**%0A * 81. Search 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,0,1,2,2,5,6%5D might become %5B2,5,6,0,0,1,2%5D).%0A *%0A * You are given a target value to search. If found in the array return true, otherwise return false.%0A *%0A * Example 1:%0A *%0A * Input: nums = %5B2,5,6,0,0,1,2%5D, target = 0%0A * Output: true%0A * Example 2:%0A *%0A * Input: nums = %5B2,5,6,0,0,1,2%5D, target = 3%0A * Output: false%0A * Follow up:%0A *%0A * This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.%0A * Would this affect the run-time complexity? How and why?%0A */%0A
 publ
@@ -49,16 +49,18 @@
  _81 %7B%0A%0A
+  
   public
@@ -85,24 +85,28 @@
 tion1 %7B%0A    
+  
+  
 public boole
@@ -137,24 +137,30 @@
 t target) %7B%0A
+      
       int st
@@ -168,16 +168,22 @@
 rt = 0;%0A
+      
       in
@@ -214,16 +214,22 @@
 %0A%0A      
+ 
+     
 //check 
@@ -273,16 +273,22 @@
 d%0A      
+   
+   
 //We alw
@@ -331,16 +331,22 @@
 t%0A      
+     
+ 
 //we can
@@ -391,16 +391,22 @@
 go next%0A
+      
       wh
@@ -422,24 +422,32 @@
 t %3C= end) %7B%0A
+        
         int 
@@ -479,16 +479,24 @@
 t) / 2;%0A
+        
         
@@ -528,24 +528,34 @@
 %7B%0A          
+       
+   
 return true;
@@ -567,19 +567,31 @@
     
-%7D%0A%0A
+        %7D%0A%0A    
         
 //if
@@ -586,16 +586,20 @@
         
+    
 //if lef
@@ -615,32 +615,40 @@
  sorted%0A        
+    
+    
 if (nums%5Bstart%5D 
@@ -664,32 +664,42 @@
 d%5D) %7B%0A          
+    
+      
 if (target %3C num
@@ -736,32 +736,44 @@
 ) %7B%0A            
+         
+   
 //target is in r
@@ -776,32 +776,44 @@
 in rotated part%0A
+            
             star
@@ -817,32 +817,42 @@
 tart = mid + 1;%0A
+          
           %7D else
@@ -858,32 +858,44 @@
 e %7B%0A            
+     
+       
 end = mid - 1;%0A 
@@ -895,34 +895,52 @@
  - 1;%0A          
+         
+ 
 %7D%0A
+        
         %7D else i
@@ -979,16 +979,26 @@
         
+      
+    
 //right 
@@ -1016,32 +1016,42 @@
 ated%0A%0A          
+    
+      
 //target is in r
@@ -1064,32 +1064,42 @@
  part%0A          
+ 
+         
 if (target %3C num
@@ -1134,32 +1134,44 @@
 ) %7B%0A            
+      
+      
 end = mid - 1;%0A 
@@ -1161,32 +1161,42 @@
  end = mid - 1;%0A
+          
           %7D else
@@ -1190,32 +1190,44 @@
        %7D else %7B%0A
+            
             star
@@ -1249,26 +1249,42 @@
         
+   
-%7D%0A
+       %7D%0A      
         
 %7D else %7B
@@ -1267,32 +1267,34 @@
 %7D%0A              
+  
 %7D else %7B%0A       
@@ -1278,32 +1278,42 @@
        %7D else %7B%0A
+          
           //dupl
@@ -1384,16 +1384,26 @@
         
+     
+     
 //based 
@@ -1479,24 +1479,34 @@
 l%0A          
+   
+       
 //thus in th
@@ -1580,24 +1580,34 @@
 n%0A          
+ 
+         
 //the runnin
@@ -1633,24 +1633,34 @@
 )%0A          
+      
+    
 start++;%0A   
@@ -1664,24 +1664,46 @@
         
+        %7D%0A            
 %7D%0A      
 %7D%0A      
@@ -1690,26 +1690,24 @@
     %7D%0A      
-%7D%0A
       return
@@ -1718,16 +1718,22 @@
 se;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 81