Array     Binary Search     Medium    

Problem Statement:

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

 

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

 

Constraints:

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • All values of nums are unique.
  • nums is an ascending array that is possibly rotated.
  • -104 <= target <= 104

Solution:

Firstly find the pivot of rotation (reference). Then find out which side the target would lie wrt pivot and search in that side.

class Solution {
public:
    int countRotations(vector<int>& nums) 
    {
        int n=nums.size(), lo=0, hi=n-1, mid;
        while (lo<=hi)
        {
            mid = lo + (hi-lo)/2;
            int prev = (mid-1+n)%n, next = (mid+1)%n;
            if (nums[mid]<=nums[prev] && nums[mid]<=nums[next])
                break;
            else if (nums[mid] <= nums[hi])
                hi = mid-1;
            else
                lo = mid+1; // nums[mid]>=nums[0]
        }
        return mid;
    }

    int search(vector<int>& nums, int target) 
    {
        int pivot = countRotations(nums);
        vector<int>::iterator it;
        if (target < nums[0] || pivot==0)
            it = lower_bound(nums.begin()+pivot, nums.end(), target);
        else
            it = lower_bound(nums.begin(), nums.begin()+pivot, target);
        if (it==nums.end()) return -1;
        if (*it==target) return it-nums.begin();
        return -1;
    }
};

TC: O(log(N))
SC: O(1)

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Search in Rotated Sorted Array.
Memory Usage: 11.9 MB, less than 28.90% of C++ online submissions for Search in Rotated Sorted Array.