[leetcode_81] Search in Rotated Sorted Array II

A variation of the previous Search in Rotated Sorted Array problem.
Original post
This time, the array allows duplicates. I modified the code’s conditional logic accordingly.
Still O(log n).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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);
    }
};