81-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.

【思路】

1.与题一的思路类似

2.不过，当A[mid]==A[left]时，就不好判断左右两部分哪边是有序的

3.当A[mid]==A[left]，若target==A[left],返回true;否则left++

【算法实现】

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