Is Search in Rotated Sorted Array easy or hard?

The problem is typically classified as Medium. Basic binary search knowledge is required, but the rotation condition adds a reasoning step where you must determine which side of the array remains sorted before deciding where to search.

Search in Rotated Sorted Array Python/Java solution

Python and Java implementations follow the same pattern: maintain left and right pointers, compute mid, detect the sorted half, and move the pointers accordingly. The logic runs in O(log n) time and uses constant extra space.

How to solve Search in Rotated Sorted Array in O(log n)?

Use binary search but first determine which half of the array is sorted. Compare nums[left], nums[mid], and nums[right] to detect the sorted segment. If the target falls within that segment, continue searching there; otherwise search the other half. This preserves logarithmic time complexity.

What is the best approach for Search in Rotated Sorted Array?

The best approach uses modified binary search that detects which half of the array is sorted during each iteration. By checking whether the target lies inside the sorted half, you can discard half of the search space every step. This keeps the runtime at O(log n) with O(1) extra space.

Is Search in Rotated Sorted Array asked at Google/Amazon/Meta?

Search in Rotated Sorted Array frequently appears in technical interviews at companies like Amazon, Google, and Meta. Interviewers use it to test binary search variations and reasoning about partially sorted arrays.

What data structure is used in Search in Rotated Sorted Array?

The problem operates directly on an array and relies on binary search logic. No additional data structures are required because the algorithm only tracks indices such as left, mid, and right while narrowing the search range.

What is the time complexity of Search in Rotated Sorted Array?

The optimal solution runs in O(log n) time because it applies binary search while handling the rotation condition. Each iteration cuts the search space in half. Space complexity stays O(1) since the algorithm uses only a few pointers.

Description Solution Video 13:28

33. Search in Rotated Sorted Array

Medium45.5% acceptance53 companies

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

Asked at top 20 of 53 companies

LinkedIn Autodesk Delhivery Wish F5 Networks Goto Newsbreak Gainsight Sixt Walmart Labs Grammarly Tinkoff

+8 more

DP World Criteo Cohesity Amazon Microsoft Bloomberg Tiktok NVIDIA

Topics

Array Binary Search

13:28

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

33. Search in Rotated Sorted Array

Asked at top 20 of 53 companies

Topics

Similar problems