81. Search in Rotated Sorted Array II Leetcode Java

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.

Solution:

Follow up for 33. Search in Rotated Sorted Array Leetcode

All related problems:
33. Search in Rotated Sorted Array
81. Search in Rotated Sorted Array II 
153. Find Minimum in Rotated Sorted Array
154. Find Minimum in Rotated Sorted Array II

Now duplicates are allowed in the array, which will make the search a little bit more tricky. For those two cases: num[mid]<num[right](right part is sorted) or num[mid]>mid[right](left part is sorted), we can still cut the search range half as problem 33 suggested. However, when num[mid]==num[right], we can't cut either half of the array, because, both of them can contain the target. Eg. target is 1. Array A: {2,2,1,2,2,2,2} and Array B: {2,2,2,2,1,2,2}, both the arrays have the property of num[mid]==num[right], but right part of A is sorted and target is in left half, while right part of B is not sorted and target is in the right half. so when this case happens, we can only guarantee that, mid number and right number is not the target, and we can't cut the range half, so the worst time complexity will increase to O(n) which we have all same elements in the array but are not the target value.

Time complexity : O(n)

 public boolean search(int[] A, int target) {  
     if(A==null || A.length==0) return false;  
     int l=0;  
     int r=A.length-1;  
     while(l<=r){  
       int m=(r-l)/2+l;  
       if(A[m]==target) return true;  
       if(A[m]<A[r]){ // right half is sorted  
         if(target>A[m] && target<=A[r]) l=m+1;  
         else r=m-1;  
       }  
       else if(A[m]>A[r]) { // left part is sorted  
         if(target>=A[l] && target<A[m]) r=m-1;  
         else l=m+1;  
       }  
       else r--;  
     }  
     return false;  
   }