Search in Rotated Sorted Array I & II

Search in Rotated Sorted Array |

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

The first one is just Binary Search. If A[start] <A[mid], it means the rotation is in the second half of the array, accordingly we can choose the start point or end point based on the target value. If A[start] > A[mid], the the rotation is in the first half.

public class SearchRotatedArray {
    public int search(int[] A, int target) {
        if (A == null)
            throw new NullPointerException("Null Array!");
        if (A.length == 0)
            return -1;
        int start = 0;
        int end = A.length - 1;
        while (start < end) {
            int mid = (start + end) / 2;
            if (A[mid] == target)
                return mid;
            if (A[start] < A[mid]) {
                if (A[start] == target)
                    return start;
                if (A[start] < target && target < A[mid]) 
                    end = mid - 1;
                else 
                    start = mid + 1;
            }
            else {
                if (target == A[end])
                    return end;
                if (A[mid] < target && target < A[end])
                    start = mid + 1;
                else
                    end = mid - 1;
            }
            
        }
        if (A[start] == target)
            return start;
        return -1;
    }
}

Search in Rotated Sorted Array ||
Duplicates allowed
The second problem. Since duplicates are allowed, A[start] <= A[mid] cannot tell if the rotation is in the first half or the second half. Of course we can separate the case to A[start] < A[mid] and A[start] == A[mid]. However, for the second case, what's next? We still have to go through every element to find the pivot, and the complexity will not be significantly less than O(n), especially for cases where there are lots of duplicates. So, why not just go through all the elements?