/ Data Structure and Algorithms  

Leetcode 33. Search in Rotated Sorted Array

Question



The original array is sorted, but rotated at some pivot index. We need to find the target value in the rotated array in O(logn). As we are looking for an O(logn) solution, we need to make use of binary search.

Similar Questions

Solution

Observe that for a given array, if we split it into half, at least one half is sorted. For example [4 5 6 7 8 1 2 3], split from 7 and get [4 5 6 7] and [8 1 2 3]. The first half is sorted.

Based on this observation, we can first find out which half is sorted (by comparing the end point values). Then check if target value is in this half. If it is, then discard the other half. If not, discard this half.

Code:

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
35
36
37
int start = 0;
int end = nums.length - 1;

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

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

    // check which side is in order by comparing end points value
    if (nums[start] <= nums[mid]) {
        // left side is in order

        // check if target in sorted half
        // because this half is sorted, just check to see if target is in range
        if (target >= nums[start] && target < nums[mid]) {
            // in this case, target in left side
            end = mid - 1;
        } else {
            // in this case, target in right side
            start = mid + 1;
        }
    } else {
        // right side is in order
        if (target > nums[mid] && target <= nums[end]) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
}

// target no found
return -1;

Time complexity O(logn), and space complexity O(1).