33. Search in Rotated Sorted Array

2020, Nov 06 2 mins read

1. Description

You are given an integer array nums sorted in ascending order, and an integer target.
Suppose that nums 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]).
If target is found in the array return its index, otherwise, return -1.

2. Example

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

Example 3:
Input: nums = [1], target = 0
Output: -1

3. Constraints

1 <= nums.length <= 5000
$-10^4$ <= nums[i] <= $10^4$
All values of nums are unique.
nums is guranteed to be rotated at some pivot.
$-10^4$ <= target <= $10^4$

4. Solutions

My Accepted Solution

n = i_nums.size()
Time complexity: O($lg_2n$)
Space complexity: O(1)

class Solution 
{
private:
    int binarySearch(const vector<int> &i_nums, int left, int right, int target) // right is the index after the last valid item, like i_nums.end() 
    {
        for(int middle = 0; left < right; )
        {
            middle = (left+right) / 2;
            
            if(i_nums[middle] == target)
                return middle;
            else if(i_nums[middle] < target)
                left = middle + 1;
            else 
                right = middle;
        }
        
        return -1;
    }
    
    int findLastRotatedSubarrayIndex(const vector<int> &i_nums)
    {
        for(int left = 0, right = i_nums.size(), middle = 0; left < right; )
        {
            middle = (left+right) / 2;
            
            if(i_nums[middle] > i_nums.back() && i_nums[middle] > i_nums[middle+1])
                return middle;
            else if(i_nums[middle] > i_nums.back())
                left = middle + 1;
            else
                right = middle;
        }
        
        return -1; // meaningless, for compile check
    }
public:
    // int search(vector<int>& nums, int target)
    int search(const vector<int> &i_nums, int target) 
    {
        // find the index of the last rotated subarray
        int lastRotatedIndex = findLastRotatedSubarrayIndex(i_nums);

        return (target <= i_nums.back() ? 
               binarySearch(i_nums, lastRotatedIndex+1, i_nums.size(), target)
               : binarySearch(i_nums, 0, lastRotatedIndex+1, target)
               );
    }
};

4.1 Binary Search - Merge Two Processes