/**
 *	Follow up for "Search in Rotated Sorted Array":
 *	What if duplicates are allowed?
 *
 *	Would this affect the run-time complexity? How and why?
 *
 *	Write a function to determine if a given target is in the array.
 *
 *	Author: matao
 */

public class SearchInRotatedSortedArrayII {
	public boolean search(int[] nums, int target) {
        for(int i = 0; i < nums.length; i++) {
            if(target == nums[i])
                return true;
        }
        return false;
    }

    public static void main(String[] args) {
    	
    }
}
@@ -293,16 +293,23 @@
 %09public 
+static 
 boolean 
@@ -348,16 +348,19 @@
 %0A       
+ //
  for(int
@@ -394,24 +394,27 @@
 +) %7B%0A       
+ //
      if(targ
@@ -428,24 +428,1079 @@
 ums%5Bi%5D)%0A    
+    //         return true;%0A        // %7D%0A        // return false;%0A        if(nums.length == 0) %7B%0A            return false;%0A        %7D%0A        int start = 0, end = nums.length - 1, mid;%0A        while(start + 1 %3C end) %7B%0A            mid = start + (end - start) / 2;%0A            System.out.println(%22start: %22 + start);%0A            System.out.println(%22mid: %22 + mid);%0A            System.out.println(%22end: %22 + end);%0A            if(nums%5Bmid%5D == target) %7B%0A                return true;%0A            %7D%0A            if(nums%5Bstart%5D %3C nums%5Bmid%5D) %7B%0A                if(nums%5Bstart%5D %3C= target && target %3C= nums%5Bmid%5D) %7B%0A                    end = mid;%0A                %7D else %7B%0A                    start = mid;%0A                %7D%0A            %7D else if(nums%5Bstart%5D %3E nums%5Bmid%5D) %7B%0A                if(nums%5Bmid%5D %3C= target && target %3C= nums%5Bend%5D) %7B%0A                    start = mid;%0A                %7D else %7B%0A                    end = mid;%0A                %7D%0A            %7D else %7B%0A                start++;%0A            %7D%0A        %7D%0A%0A        if(nums%5Bstart%5D == target %7C%7C nums%5Bend%5D == target) %7B%0A
             
@@ -1540,24 +1540,25 @@
 turn false;%0A
+%0A
     %7D%0A%0A    p
@@ -1602,16 +1602,92 @@
  %7B%0A    %09
+int%5B%5D nums1 = %7B2, 2, 2, 3, 1%7D;%0A        System.out.println(search(nums1, 1));
 %0A    %7D%0A%7D

optimize solution