@@ -0,0 +1,1468 @@
+// Follow up for %22Search in Rotated Sorted Array%22:%0A// What if duplicates are allowed?%0A%0A// Would this affect the run-time complexity? How and why?%0A%0A// Write a function to determine if a given target is in the array.%0A%0Apublic class Solution %7B%0A    public boolean search(int%5B%5D A, int target) %7B%0A        int len = A.length;%0A%0A        if(len == 0) return false;%0A%0A        int left = 0;%0A        int right = len - 1;%0A%0A        while(left %3C= right)%7B%0A            int mid = (left + right) / 2;%0A%0A            if(A%5Bmid%5D == target) return true;%0A%0A            if(A%5Bmid%5D %3C A%5Bright%5D)%7B%0A                // if right half is sorted%0A                if(target %3C= A%5Bright%5D && target %3E A%5Bmid%5D)%7B%0A                    // if target is in the right half%0A                    left = mid + 1;%0A                %7Delse%7B%0A                    // if target is not in the right half, we cut it.%0A                    right = mid - 1;%0A                %7D%0A            %7Delse if(A%5Bmid%5D %3E A%5Bleft%5D)%7B%0A                // if left half is sorted%0A                if(A%5Bmid%5D %3E target && A%5Bleft%5D %3C= target)%7B%0A                    // if target is in the right half%0A                    right = mid - 1;%0A                %7Delse%7B%0A                    // if target value is not in the right half.%0A                    left = mid + 1;%0A                %7D%0A            %7Delse if(A%5Bmid%5D == A%5Bright%5D)%7B%0A                right--;%0A            %7Delse if(A%5Bmid%5D == A%5Bleft%5D)%7B%0A                left++;%0A            %7D%0A        %7D%0A%0A        return false;        %0A    %7D%0A%7D

add search in rotated sorted array ii solution