首页 » 编程之美 » 正文

[leetcode_81]Search in Rotated Sorted Array II

leetcode_60题目的变形
http://blog.sina.com.cn/s/blog_672f71fc0101pgf6.html
这次,array允许重复的。我适当改了下代码判断的情况。
仍然是o(logn)

class Solution {
public:
    bool searchStep(int A[],int target,int left,int right) 
    {
        if(left > right)
            return false;
        int mid = (left+right)/2;
        if(A[mid] == target)
            return true;
        else
            if(A[mid] > target)
            {
                if(A[right] > A[left])
                    return searchStep(A,target,left,mid-1);
                else
                    return searchStep(A,target,left,mid-1) || searchStep(A,target,mid+1,right);
            }
            else
            {
                if(A[right] > A[left])
                    return searchStep(A,target,mid+1,right);
                else
                    return searchStep(A,target,mid+1,right) || searchStep(A,target,left,mid-1);
            }
    }
    bool search(int A[], int n, int target) 
    {
        int left = 0;
        int right = n-1;
        return searchStep(A,target,left,right);
    }
};

发表评论