33. Search in Rotated Sorted Array

Search in Rotated Sorted Array (LeetCode 33) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Binary Search Patterns pattern, in the Find Min/Max in Rotated Sorted Array subpattern.

• Blind 75 · #18 of 75 · Binary Search
• NeetCode 150 · #32 of 150 · Binary Search
• NeetCode 250 · #68 of 250 · Binary Search

How to solve Search in Rotated Sorted Array

Search in Rotated Sorted Array is a Binary Search in Rotated Sorted Array problem, part of Binary Search Patterns. Master binary search in rotated sorted arrays. Find minimum, search elements, and handle duplicates.

Work towards the solution in these steps:

1. Consider how binary search can be adapted to work efficiently on arrays that are not fully sorted in the traditional sense.
2. Observe that even though the array is rotated, one half of the array (left or right) remains sorted at any point during your search.
3. Use the fact that the sorted half can help determine whether the target lies within that half or the other half, guiding your search boundaries.

The reference solution runs in O(logn) time and O(1) space.

The Search in Rotated Sorted Array solution and editorial walks through the full approach with reference code.

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

Topics and companies

Topics: Array, Binary Search.

Reported in interviews at Amazon, Facebook, Microsoft, LinkedIn, Oracle, Apple, Bloomberg, Nvidia, Expedia, Google, Adobe, Zillow and others.

How to practise Search in Rotated Sorted Array on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(logn) time and O(1) space.

Open Search in Rotated Sorted Array in the code editor, or read the Search in Rotated Sorted Array editorial for a worked solution with its approach and complexity analysis.

Where Search in Rotated Sorted Array sits in the DSA pattern sheet

• Binary Search Patterns pattern guide
• Find Min/Max in Rotated Sorted Array subpattern
• The full DSA patterns sheet

Problems related to Search in Rotated Sorted Array

Other problems that use the same Find Min/Max in Rotated Sorted Array and Binary Search Patterns techniques:

• Find in Mountain Array — Hard, same subpattern
• Find Minimum in Rotated Sorted Array — Medium, same subpattern
• Find Peak Element — Medium, same subpattern
• Peak Index in a Mountain Array — Medium, same subpattern
• Search in Rotated Sorted Array II — Medium, same subpattern
• Binary Search — Easy, same pattern

Search in Rotated Sorted Array FAQ