Leetcode: 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.

Understand the problem:
The problem is an extension to the I. Since duplicates exist in the array, cutting the array into two halves will not work. Consider [1,3,1,1,1], target is 3, it will not find the targeted number. 

Solution:

public class Solution {
    public boolean search(int[] A, int target) {
        if (A == null || A.length == 0) {
            return false;
        }
        
        int lo = 0;
        int hi = A.length - 1;
        
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (A[mid] == target) {
                return true;
            }
            
            if (A[lo] < A[mid]) {
                if (A[lo] <= target && target < A[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else if (A[lo] > A[mid]) {
                if (A[mid] < target && target <= A[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            } else {
                lo++;
            }
        }
        
        return false;
    }
}

Update on 9/29/14:
If we directly use the original code from problem I, we will get errors. For example, for the input array [1, 3, 1, 1, 1], and target = 3. Now the situation is A[lo] = A[mid] = A[hi], so we are unable to say the first half is in ascending order. 

Code (Java):

public class Solution {
    public boolean search(int[] A, int target) {
        if (A == null || A.length == 0) {
            return false;
        }
        
        int lo = 0;
        int hi = A.length - 1;
        
        while (lo + 1 < hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (A[mid] == target) {
                return true;
            }
            
            if (A[lo] < A[mid]) {
                if (A[lo] <= target && target < A[mid]) {
                    hi = mid;
                } else {
                    lo = mid;
                }
            } else if (A[lo] > A[mid]) {
                if (A[mid] < target && target <= A[hi]) {
                    lo = mid;
                } else {
                    hi = mid;
                }
            } else {
                lo++;
            }
        }
        
        if (A[lo] == target || A[hi] == target) {
            return true;
        }
        
        return false;
    }
}

The take-away message for this problem:
1. Figure out why the solution of problem 1 won't work. Take out an opposite example. 
A = [3, 1, 2, 3, 3, 3, 3], where A[lo] == A[mid] == A[hi]
2. Analyze the time complexity in worst case, why it is O(n). Take an example. 
A = [1, 1, 1, 1, 1, 1], where target = 2, then you need to iterate all elements of the array
A = [1, 1, 1, 1, 1, 0], where the target = 0, then you need to iterate all elements as well.

Updates on 11/20/14:

public class Solution {
    public boolean search(int[] A, int target) {
  if (A == null || A.length == 0) {
   return false;
        }

        int lo = 0;
        int hi = A.length - 1;
        while (lo + 1 < hi) {
         int mid = lo + (hi - lo) / 2;
         if (A[mid] == target) {
             return true;
            }
         
         if (A[lo] < A[mid]) {
          if (target >= A[lo] && target < A[mid]) {
                 hi = mid;
                } else {
                 lo = mid;
                }
                
            } else if (A[mid] < A[hi]) {
             if (target > A[mid] && target <= A[hi]) {
              lo = mid;
                } else {
                 hi = mid;
                }
            } else {
                if (A[lo] == target) {
                    return true;
                }
             lo++;
            }
        }
        if (A[lo] == target || A[hi] == target) {
         return true;
        } else {
         return false;
        }
    }
}

The difference is to check A[mid] < A[hi] meaning right half is sorted. 
The second difference is when we move the left pointer one step ahead, we need to check if it is equal to the target.