Day 81, #81, Search in Rotated Sorted Array II

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.
--------------------------------------------------------------------------
与I同样的思路，不同点是增加了1个if判断来解决重复的问题
重复的情况#1： start，mid，end 3处都相等，如111111111111112111。此时左右两半都需要检测，worst cast O(n)
重复的情况#2：仅start或者end跟mid相等，如4444123，此时原有代码也可解决

class Solution {
public:
    bool searchInRotated(int A[], int start, int end, int target) {
        if (start > end) {
            return false;
        }
        int mid = (start + end) / 2;
        if (A[mid] == target) {
            return true;
        }
        
        // ------ to handle duplicates ---- 
        if (A[start] == A[mid] && A[start] == A[end]) {
            return searchInRotated(A,start,mid - 1,target) || searchInRotated(A,mid + 1,end,target);
        }
        
        if (A[start] <= A[mid]) {
            if (A[start] <= target && target <= A[mid]) {
                return searchInRotated(A,start,mid - 1,target);
            }else {
                return searchInRotated(A,mid + 1,end,target);
            }
        }else {
            if (A[mid] <= target && target <= A[end]) {
                return searchInRotated(A,mid + 1,end,target);
            }else {
                return searchInRotated(A,start,mid - 1,target);
            }
        }
        
    }

    bool search(int A[], int n, int target) {
        return searchInRotated(A,0,n - 1,target);
    }
};

Solution #2, iterative(to do)