Leet Code: search in rotated sorted array with duplicate...

Search in Rotated Sorted Array II

 

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.

This one is not difficult to find the trick, 
but if you think in a wrong way, you will use a lot of effort to ignore duplicate items..

* If you just think on the index, you don't need recursive...
* In each loop, change l and f in order to find a right region to go on searching...

public class Solution {
    
    public boolean search(int[] A, int target) {
        
        int f=0;
        int l=A.length-1;
        
        while(l>=f)
        {
            int m=(f+l)/2;
            if(A[m]==target)
                return true;

            if(A[f]<A[m])
            {
                if(target>=A[f]&&target<=A[m])
                    l=m-1;
                else
                    f=m;
            }
            else if(A[f]>A[m])
            {
                if(target>=A[m]&&target<=A[l])
                    f=m+1;
                else
                    l=m;
            }
            else            
                f++;              // Trick: A[f]==A[m])
        }
        return false;

    }
}