<33> Search in Rotated Sorted Array

Posted on Edited on In Views:

Description

Question: 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).

Leetcode link: 33. Search in Rotated Sorted Array

Idea

If we list all possible rotation of an array, we can notice below attributes:

  • If the middle value is smaller than the rightmost element, than the sequence from the middle to the rightmost is ascending.
  • Otherwise, the sequence from the leftmost to the middle is ascending.

Based on above attributes, we can further know if the target is right or left to the middle. If the target is larger than the middle but smaller than the rightmost value, the left bound should be shrinked. Otherwise, the right bound should be moved to left.

Test cases

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

Solution

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
class Solution {
    int[] arr;
    int target;
    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;
            if (nums[mid] < nums[right]) {
                if (nums[mid] < target && target <= nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            } else {
                if (nums[left] <= target && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
        }
        return -1;
    }
}