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.

http://www.lintcode.com/en/problem/search-in-rotated-sorted-array-ii/

Discussion

见Search in Rotated Sorted Array的讨论。

Solution

class Solution {
    /** 
     * param A : an integer ratated sorted array and duplicates are allowed
     * param target :  an integer to be search
     * return : a boolean 
     */
public:
    bool search(vector<int> &A, int target) {
        // write your code here
        int n = A.size();
        if(n ==0) return false;
        int start = 0;
        int end = n-1;
        int mid;
        while(start + 1 < end) {
            mid = start + (end-start)/2;
            if(A[mid] == target)//也可以不用这里return.
                return true;
            if(A[start]< A[mid]) {
                if(A[start] <= target && target <= A[mid]) {
                   end = mid; 
                } else {
                    start = mid;
                }

            } else if(A[start]> A[mid]) {
                if(A[mid] <= target && target <= A[end]) {
                    start = mid;
                } else {
                    end = mid;
                }
            } else {
                start++;
            }
        }
        if(A[start] == target)
            return true;
        if(A[end] == target)
            return true;
        return false;    
    }
};

改进版：

class Solution {
    /** 
     * param A : an integer ratated sorted array and duplicates are allowed
     * param target :  an integer to be search
     * return : a boolean 
     */
public:
    bool search(vector<int> &A, int target) {
        if(A.empty()) return false;
        int start = 0;
        int end = A.size() - 1;
        while(start + 1 < end) {
            int mid = start + (end-start)/2;
            if(A[mid] < A[end]) {
                end = mid;
            } else if(A[mid] > A[end]){
                start = mid; 
            } else {
                end--;
            }
        }
        int pivot = -1;
        if(A[start] < A[end]) pivot = start;
        else pivot = end;
        int idx = binarySearch(A, 0, pivot - 1, target);
        if(idx != -1) return true;
        else return (binarySearch(A, pivot, A.size() - 1, target) != -1);
    }
    int binarySearch(vector<int> &A, int start, int end, int target) {
        while(start + 1 < end) {
            int mid = start + (end-start)/2;
            if(A[mid] < target) {
                start = mid;
            } else {
                end =  mid;
            }
        }
        if(A[start] == target) return start;
        if(A[end] == target) return end;
        return -1;
    }
};

这个改进版其实是有问题的，在lintcode上没有报错，在leetcode上报错了。比如”1 1 1 1 2 1 1“，找出来的pivot是第一个1， 因为根据 Find Minimum in Rotated Sorted Array II， 找到是第一个minimum出现的位置，而不是真正的pivot的位置。这两个不矛盾，最小值未必就是pivot，但pivot一定是最小值。 所以这里在找pivot的时候不能end--从右向左，而应该从左向右start++，下面是AC的程序：

class Solution {
public:
    bool search(vector<int> &A, int target) {
        if (A.empty()) return false;
        int start = 0;
        int end = A.size() - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (A[mid] < A[start]) {
                end = mid;
            }
            else if (A[mid] > A[start]){
                start = mid;
            }
            else {
                start++;
            }
        }
        int pivot = -1;
        if(A[start] <= A[end]) pivot = start;
        else pivot = end;
        int idx = binarySearch(A, 0, pivot - 1, target);
        if(idx != -1) return true;
        else return (binarySearch(A, pivot, A.size() - 1, target) != -1);
    }
    int binarySearch(vector<int> &A, int start, int end, int target) {
        if(start > end) return -1;
        while(start + 1 < end) {
            int mid = start + (end-start)/2;
            if(A[mid] < target) {
                start = mid;
            } else {
                end =  mid;
            }
        }
        if(A[start] == target) return start;
        if(A[end] == target) return end;
        return -1;
    }
};