Search in Rotated Sorted Array

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

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

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:

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

Example 2:

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

You may view the full question here.

Approach 1: Consider the example — [0,2,3,4,5,6,7,9] becoming [4,5,6,7,9,0,2,3] . We can represent the rotated array in the following manner —

Pictorial representation

We can see two parts — the head and the tail of the sorted array. And these are placed in the order as shown in the picture as it is rotated around a pivot, in our case around 4. The point where the Tail part ends and the Head part begins, indicated by the red arrow is the only point where the previous element is greater than the current element.

The solution is designed around the following points —

• Identify which part to search — head or tail (only one of these, not both)
• the end of the tail or the head is identified by the transition as marked by the red arrow

Let’s quickly dive into the code —

//Approach 1:
//Runtime: 0ms
//Memory usage: 37MB
class Solution {
    public int search(int[] nums, int target) {
        if(nums.length==0){
            return -1;
        }
        if(target<nums[0]){
            return searchEnd(nums, target);
        } else {
            return searchStart(nums, target);
        }
    }
    
    private int searchStart(int[] nums, int target){
        int prev;
        int curr = nums[0];
        if(curr==target) return 0;
        for(int i = 1; i<nums.length; i++){
            prev = curr;
            curr = nums[i];
            if(prev>curr){
                break;
            } else if(curr==target){
                return i;
            }
        }
        return -1; 
    }
    
    private int searchEnd(int[] nums, int target){
        int prev;
        int curr = nums[nums.length-1];
        if(curr==target) return nums.length-1;
        for(int i = nums.length - 2; i>0; i--){
            prev = curr;
            curr = nums[i];
            if(prev<curr){
                break;
            } else if(curr==target){
                return i;
            }
        }
        return -1; 
    }
}

Find more posts here.

Cheers & Chao!