[LeetCode] 33. Search in Rotated Sorted Array

Posted on | In

Problem

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of $O(\log n)$.

Example 1:

1
2
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

1
2
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Explanation

  1. For example, the array is [3, 4, 5, 6, 7, 8, 9, 1, 2], the middle element is 7. We can draw the graph like below:

    1
    2
    3
    4
    5
    6
    7
    8
    9
                       /
                 /
               /(mid)
             /
           /
         /
       /(left = 3)
                      /(right = 2)
                     /

  2. We need to consider two cases, case1, the mid is greater than left, case2 is the mid is less than left. The above example is case1. In case1, if the target is greater than left and target is less than mid, then we can set right = mid, else, we set left = mid. Then, we recusivly find the mid and check again. In case2, if target is less than right and target is greater than mid, then we can set left = mid, else, we set right = mid. Then, we also recursivly find the mid and check again.

  3. When the left and right is next to each other, we can break out the loop, and check left and right individually. If not found the target, we return -1.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        int left = 0, right = nums.length - 1;
        while(left+1 < right) {
            int mid = left + (right-left)/2;
            if (target == nums[mid]) return mid;
            if (nums[mid] > nums[left]) {
                if (target >= nums[left] && target <= nums[mid]) right = mid;
                else left = mid;
            } else {
                if (target >= nums[mid] && target <= nums[right]) left = mid;
                else right = mid;
            }
        }
        if (nums[left] == target) return left;
        if (nums[right] == target) return right;
        return -1;
    }
}

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (target == nums[mid]) return mid;
            if (nums[mid] >= nums[left]) {
                if (target >= nums[left] && target <= nums[mid]) right = mid;
                else left = mid + 1;
            } else {
                if (target >= nums[mid] && target <= nums[right]) left = mid + 1;
                else right = mid;
            }
        }
        return -1;
    }
}