/ Data Structure and Algorithms  

Leetcode 81. Search in Rotated Sorted Array II

Question



Follow up question on 33. Search in Rotated Sorted Array. This time the array may contain duplicates

Similar Questions

Solution

For this question we can extend the solution from 33. Search in Rotated Sorted Array. The algorithm is based on the fact that after splitting an array from any position, it is at least half sorted.

For example, [4 5 6 7 1 2 3], and split from 7, the left is [4 5 6 7], the right is [7 1 2 3]. So the left part is ordered.

We can find out which part is in order (by comparing the endpoints). Knowing which part is in order, all we need is the normal binary search and check if the target is in this part. If it is, Then discard the other half. If not, discard this half.

That is the approach we used for 33. Search in Rotated Sorted Array. With this question, we need a slight modification. As for this question, we have duplicates in the array. So when we decide which part is in order, there is a problem.

For example, nums = [ 1, 3, 1, 1, 1 ] and targer = 3. The left half is [1, 3, 1]. By comparing endpoints nums [start] <= nums [mid], the algorithm thinks that left half is in order, which is not the case.

So we need to take nums[start] == nums[mid] as a special case. The solution is quite simple, just start++ will do.

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
33
34
int start = 0;
int end = nums.length - 1;

while (start <= end) {
    int mid = (start + end) / 2;

    // find target
    if (target == nums[mid]) {
        return true;
    }

    // left side is ordered
    if (nums[start] < nums[mid]) {
        // target in left side
        if (target >= nums[start] && target <= nums[mid]) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    // special case like [1, 3, 1]
    } else if (nums[start] == nums[mid]) {
        start++;
    // right side is ordered    
    } else {
        // target in right side
        if (target >= nums[mid] && target <= nums[end]) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
}

return false;