33. Search in Rotated Sorted Array

LeetCode

Divide and Binary Search (2 times)

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
38
39
40
41
42
43
44
45
46
47
class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        // if sorted
        if (nums[0] <= nums[n - 1]) return binarySearch(nums, 0, n - 1, target);

        // find the division index

        int left = 0;
        int right = n - 1;
        int pivot = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid < n - 1 && nums[mid] > nums[mid + 1]) {
                pivot = mid;
                break;
            }
            if (nums[mid] >= nums[left]) {
                left = mid + 1;  // pivot on right
            } else {
                right = mid - 1; // pivot on left
            }
        }

        if (target >= nums[0]) {
            return binarySearch(nums, 0, pivot, target);
        } else {
            return binarySearch(nums, pivot + 1, n - 1, target);
        }

    }


    private int binarySearch(int[] nums, int start, int end, int target) {
        while (start <= end) {
            int pos = (start + end) / 2;
            if (nums[pos] == target) {
                return pos;
            } else if (nums[pos] > target) {
                end = pos - 1;
            } else {
                start = pos + 1;
            }
        }
        return -1;
    }
}

Remarks:

  1. TC: $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
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) return mid;

            // check which side is sorted
            if (nums[left] <= nums[mid]) {
                // left side sorted
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1; // search in left half
                } else {
                    left = mid + 1;  // search in right half
                }
            } else {
                // right side sorted
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;  // search in right half
                } else {
                    right = mid - 1; // search in left half
                }
            }
        }

        return -1;
    }
}

Same SC. (but actually half time)