Search in Rotated Sorted Array Cont…

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 2: Borrowing a few concepts from the previous approach. 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.

What we missed in the previous approach was the time complexity indicated in the problem statement. The solution should cost us no more than O(log n). One way to achieve this time complexity is by adopting the approach used in our trusty Binary Search Algorithm! Here is a simple program using this approach by simply tweaking the condition logic to account for the rotated array —

//Approach 2:
//Runtime: 0ms
//Memory usage: 39.1MB
class Solution {
    public int search(int[] nums, int target) {
        for(int start = 0, end = nums.length -1, mid = (start + end)/2; start <= end; mid = (start+end)/2){
            if(nums[mid] == target){
                //FOUND element
                return mid;
            }
            if(start==end){
                break;
            }
            if(mayBePresent(nums[start], nums[mid], target)){
                //search first half
                end = mid;
            } else if(mayBePresent(nums[mid+1], nums[end], target)){
                //search second half
                start = mid+1;
            } else {
                //present in neither
                break;
            }
        }
return -1;
}
boolean mayBePresent(int startItem, int endItem, int target){
        if(startItem <= endItem){
            //Not rotated
            if(startItem <= target && target <= endItem){
                return true;
            }
        } else if(startItem > endItem){
            //Rotated
            if(startItem <= target || target <= endItem){
                return true;
            }
        }
        //for everything else
        return false;
    }
}

Find more posts here.

Cheers & Chao!