Search in Rotated Sorted Array II

Description

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.

Example

Given [1, 1, 0, 1, 1, 1] and target = 0, return true.

Given [1, 1, 1, 1, 1, 1] and target = 0, return false.

Related problems

Find Minimum in Rotated Sorted Array II

Medium Find Minimum in Rotated Sorted Array

Medium Search in Rotated Sorted Array II

Medium Search in Rotated Sorted Array

Implementation

Link: http://lintcode.com/en/problem/search-in-rotated-sorted-array-ii/

class Solution {
    /** 
     * param A : an integer ratated sorted array and duplicates are allowed
     * param target :  an integer to be search
     * return : a boolean 
     */
public:
    bool search(vector<int> &A, int target) {
        // write your code here
        if(A.size() == 0) return 0;

        int left = 0;
        int right = A.size() - 1;

        while(left + 1 < right){
            int mid = left + (right - left)/2;
            if(A[mid] == target){
                return true;
            }

            if(A[mid] == A[left]){
                left++;
            }else if(A[mid] == A[right]){
                right--;
            }else if(A[mid] > A[left]){
                if(A[left] <= target && target < A[mid]){
                    right = mid;
                }else{
                    left = mid;
                }
            }else{ // A[mid] < A[left]
                if(A[mid] < target && target <= A[right]){
                    left = mid;
                }else{
                    right = mid;
                }
            }
        }

        if(A[left] == target) return true;
        if(A[right] == target) return true;
        return false;
    }
};