Search in Rotated Sorted Array II

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

A:

-----------------------第二遍-------------不管不顾pivot点， 思想跟问题一一样，就是通过看begin 和end两个位置的点的值，如果前者 < 后者， 正常顺序，二分查找。

如果A[begin] >= A[end]   这个区间，含有pivot ， 二分查找的，两部分都要查。

最终还是  O(n)

public class Solution {
    public boolean search(int[] nums, int target) {
        return search(nums, 0,nums.length-1,target);
    }
    private boolean search(int[] A, int begin, int end, int target){
        if(begin > end)
            return false;
        int mid = (begin+end)/2;
        if(A[mid]==target)// check this pivot position
            return true;
        if(A[begin]<A[end])
            return A[mid]>target?search(A,begin,mid-1,target):search(A,mid+1,end,target);
        else // may need search two sides
            return search(A,begin,mid-1,target) || search(A,mid+1,end,target);
    }
}

就是把1 的方法copy过来，然后，把所有的return 中的 -1 换成 false, i 换成true。即可------------但思想还是先找到pivot下标。需要遍历，这样是不对的

public class Solution {
    public boolean search(int[] A, int target) {
        // assume A is sorted in ascending order
        if (A.length == 0)
            return false;
        int pivotIndex = -1;
        // find pivot while searching
        if (A[0] == target) {
            return true;
        }
        if (A[0] < target) {
            // search the first half part
            int i = 1;
            while (i < A.length) {
                if (A[i] < A[i - 1]) {
                    // i+1 is the pivot,
                    // pivotIndex = i;
                    return false; // not need to continue search
                }
                if (A[i] == target) {
                    return true;
                } else if (A[i] < target) {
                    i++;
                } else { // A[i] > target
                    return false; // do not exist in A
                }
            }
        } else { // A[0] > target , ----> search the left half part
                    // find pivot , because the first rotated part are all >
                    // target
            int i = 1;
            while (i < A.length) {
                if (A[i] < A[i - 1]) {
                    pivotIndex = i;
                    break;
                } else {
                    i++;
                }
            }
            // search from pivotIndex;
            i = Math.max(0, pivotIndex);
            while (i < A.length) {
                if (A[i] == target) {
                    return true;
                } else if (A[i] < target) {
                    i++;
                } else { // A[i] > target
                    return false;
                }
            }
        }
        return false; // need when A[0]> target, and all a[i]<target
    }
}