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. http://leetcode.com/onlinejudge#question_33

leetcode_search_in_rotated_sorted_array_2.cpp

bool bsearch(int A[], int left, int right, int target) {
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (A[mid] > target)
            right = mid - 1;
        else if (A[mid] < target)
            left = mid + 1;
        else
            return true;
    }
    return false;
}

int get_biggest(int A[], int left, int right) {
    if (A[left] < A[right] || left == right)
        return right;
    else if (A[left] == A[right]) {
        int mid = (left + right) >> 1;
        int l = get_biggest(A, left, mid);
        int r = get_biggest(A, mid + 1, right);
        return A[l] >= A[r] ? l : r;
    }
    else {
        int ret = left;
        int l = left, r = right;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (A[mid] >= A[left]) {
                ret = max(ret, mid);
                l = mid + 1;
            }
            else
                r = mid - 1;
        }
        return ret;
    }
}

class Solution {
public:
    bool search(int A[], int n, int target) {
        if (n == 0)
            return false;
        if (A[0] < A[n - 1])
            return bsearch(A, 0, n - 1, target);
        else {
            int bigid = get_biggest(A, 0, n - 1);
            if (target >= A[0])
                return bsearch(A, 0, bigid, target);
            else
                return bsearch(A, bigid + 1, n - 1, target);
        }
    }
};