033.Search in Rotated Sorted Array

Posted on | In

Test cases

1
2
3
4
5
6
7
8
[1]
0
[1]
1
[]
5
[1,3]
3

Solution 1: 14ms

Binary solution.
Time: O(logN)
Space: O(1) 

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
public int search(int[] nums, int target) {
    if(nums.length == 1) return target == nums[0]? 0 : -1;      
    int start = 0;
    int end = nums.length - 1;
    while (start <= end) { // "=" for case nums.length == 1
        int mid = start + (end - start) / 2;
        if (nums[mid] == target) return mid;
        // if the left side is sorted
        if (nums[start] <= nums[mid]) { // "=" for case nums.length == 1 or 2
            // if the target is also on the left side
            if (target < nums[mid] && target >= nums[start]) 
                end = mid - 1;
            // if the target is on the right side
            else 
                start = mid + 1;
        // if the right side is sorted
        } else if (nums[mid] <= nums[end]) {
            // if the target is also on the right side
            if (target > nums[mid] && target <= nums[end]) 
                start = mid + 1;
            // if the target is on the left side
            else 
                end = mid - 1;
        } else // problems with the given array
            return -1;
    }
    return -1;
}
Alternative
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
public int search(int[] nums, int target) {
    if (nums.length == 0) return -1;
    if (nums.length == 1) 
        return target == nums[0]? 0 : -1;
    int lo = 0;
    int hi = nums.length - 1;
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) 
            return mid;
        if (nums[mid] > nums[lo]) {
            if (target >= nums[lo] && target < nums[mid]) 
                hi = mid;
            else 
                lo = mid;
        } else if (nums[mid] < nums[hi]) {
            if (target <= nums[hi] && target > nums[mid])
                lo = mid;
            else 
                hi = mid;
        } else {
            return -1;
        }
    }
    if (nums[lo] == target) return lo;
    if (nums[hi] == target) return hi;
    return -1;
}