Leetcode 81: Search in Rotated Sorted Array II

Problem:

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:

Based on the analysis of  "Search in Rotated Sorted Array", we are unable to make sure which part

is sorted only by comparing the mid with the left element. In this case, we need to increase the left

pointer until it is not equal to the mid.

Related questions:

Leetcode 33: Search in Rotated Sorted Array

Code:

public class Solution {
    public boolean search(int[] A, int target) {
        if(A==null || A.length==0 || A.length==1 && A[0]!=target){
            return false;
        }
        int left=0;
        int right=A.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(target==A[mid]){
                return true;
            }else if(A[left]<A[mid]){
                if(A[left]<=target && target<A[mid]){
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }else if(A[left]>A[mid]){
                if(A[mid]<target && target <=A[right]){
                    left=mid+1;
                }else{
                    right=mid-1;
                }
            }else{
                left++;
            }
        }
        return false;
    }
}