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.


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

=========

public class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int s = 0;
        int e = nums.length - 1;
        while (s <= e) {
            int m = (s + e) / 2;
            if (nums[m] == target) {
                return true;
            } else {
                // left is sorted
                boolean leftSorted = true;
                for (int i = s; i < m; i++) {
                    if (nums[i] > nums[i+1]) {
                        leftSorted = false;
                        break;
                    }
                }
                if (leftSorted) {
                    if (target >= nums[s] && target <= nums[m]) {
                        e = m - 1;
                    } else {
                        s = m + 1;
                    }
                } else {
                    if (target >= nums[m] && target <= nums[e]) {
                        s = m + 1;
                    } else {
                        e = m - 1;
                    }
                }
            }
        }
        return false;
    }
}