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.

---------------------- thinking -------------------------

---------------------------- codes --------------------------------
class Solution {
public:
    bool search(int A[], int n, int target) {
        if (n == 0) {
            return false;
        }
        searchHelper(A, 0, n-1, target);
    }
 
    bool searchHelper(int A[], int start, int end, int target) {
        if (start == end) {
            if (A[start] == target) {
                return true;
            } else {
                return false;
            }
        }
        if (start + 1 == end) {
            if (A[start] == target || A[end] == target) {
                return true;
            } else {
                return false;
            }
        }
         int mid = start + (end - start)/2;
        if (A[mid] == target) {
            return true;
        }
        if (target > A[start] && (A[mid] < A[start] || A[mid] > target)) {
            return searchHelper(A, start, mid - 1, target);
        } else if (target < A[start] && (A[mid] > A[start] || A[mid] < target)) {
            return searchHelper(A, mid + 1, end, target);
        } else {
            return searchHelper(A, start, mid, target) || searchHelper(A, mid + 1, end, target);
        }
    }
};

-------------------------- iterative methods --------------------------------
class Solution {
public:
  bool search(int A[], int n, int target) {
    int lo =0, hi = n-1;
    int mid = 0;
    while(lo<hi){
          mid=(lo+hi)/2;
          if(A[mid]==target) return true;
          if(A[mid]>A[hi]){
              if(A[mid]>target && A[lo] <= target) hi = mid;
              else lo = mid + 1;
          }else if(A[mid] < A[hi]){
              if(A[mid]<target && A[hi] >= target) lo = mid + 1;
              else hi = mid;
          }else{
              hi--;
          }

    }
    return A[lo] == target ? true : false;
  }
};