Leetcode: Search in a sorted array that can have duplicates

duplicate_rotated_array_search.cpp

/*
 * This is the classic problem, but made slightly more difficult by allowing duplicates. If duplicates are allowed,
 * then we can get into a pickle: When both the first and last element are the same. In this case, we do not know whether to go 
 * forwards or backwards. What do we know: That both first and last are the same (duh)! So that basically means we carry 
 * on either ignoring the first element or the last element (they are the same after all, so it does not matter).
 *
 * Time complexity = O(N) (bye bye logn binary search). This is because in the worst case, line 28 comes down to
 * a linear search.
 */


class Solution {
public:
    bool search(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        if (n==0) {
            return false;
        }
        
        int half = (n-1) / 2,
            first = A[0],
            last = A[n-1];
        

        if (n >= 2 && A[half] == first && A[half] == last) {
            return search(A, n-1, target);
        }
        
        if (A[half] < target) { //We want to go forwards
            if (first > A[half] && last < target) { //go backwards
                return search(A, half, target);
            }
            
            return search(A+half+1, n-half-1, target);
        }
        
        if (A[half] > target) { //We want to go backwards
            if (last < A[half] && first > target) { //go forwards
                return search(A+half+1, n-half-1, target);
            }
            return search(A, half, target);
        }
        
        return true;
    }
};