[LeetCode] Search in Rotated Sorted Array II

Link : Search in Rotated Sorted Array II

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.




Analysis:

Quite similar to the problem  [LeetCode] Search in Rotated Sorted Array

Boundary need more careful handling.
The point is what if A[low] == A[mid], one possible case is that that are in the same section, which is good.
The other possible case will be they are at different sections, and this make the spots between them invisible.
So every time we meet A[low]==A[mid], we decrease mid until low == mid or A[low]!=A[mid].

Code says!

 class Solution {  
 public:  
   bool search(int A[], int n, int target) {  
     if(n<=0)  
       return false;  
     int low=0, mid, high=n-1;  
     while(low<=high)  
     {  
       mid = (low+high)/2;  
       if(A[mid]==target) return true;  
       if(A[mid]==A[low])  
         while(A[low]==A[mid]&&low<mid) mid--;  
       if(A[mid]>=A[low])  
       {  
         if(A[low]<=target && target<=A[mid])  
           high = mid;  
         else  
           low = mid+1;  
       }  
       else  
       {  
         if(A[mid]<=target && target<=A[high])  
           low = mid;  
         else  
           high = mid-1;  
       }  
     }  
     return false;  
   }  
 };