DEV Community

late_riser
late_riser

Posted on

Search in Rotated Sorted Array (Leetcode 33)

Search in Rotated Sorted Array (Leetcode 33)Problem
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(logn) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Enter fullscreen mode Exit fullscreen mode
Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Enter fullscreen mode Exit fullscreen mode
Example 3:

Input: nums = [1], target = 0
Output: -1
Enter fullscreen mode Exit fullscreen mode

Source: Leetcode

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
Enter fullscreen mode Exit fullscreen mode

How to solve this interesting problem?

If a sorted array is not rotated, it is easy to find a target value using Binary Search algorithm. Because, we know the target value will be somewhere between the first and the last element of the array. But if we rotate the array, the array no longer remains sorted, right?

Read more in our blog Foolish Hungry dot com ... :)

Top comments (0)