DEV Community

late_riser
late_riser

Posted on

2 1

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)

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay