Skip to content

Search in Rotated Sorted Array⚓︎

Link

Description⚓︎

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
  • -10^4 <= nums[i] <= 10^4
  • All values of nums are unique.
  • nums is an ascending array that is possibly rotated.
  • -10^4 <= target <= 10^4

Solution⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = -1, r = nums.size();
        while (l + 1 < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= nums[0]) l = mid;
            else r = mid;
        }

        if (target >= nums[0]) r = l + 1, l = -1;  // "r = l" can also pass the test, but "r = l + 1" is better
        else r = nums.size();

        while (l + 1 < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid;
        }

        if (r < nums.size() && nums[r] == target) return r;
        else return -1;
    }
};