Skip to main content
Talentd

Search in Rotated Sorted Array - Solution & Explanation

MediumArrayBinary Search27 min readAsked at: Amazon, Microsoft, Apple +50
Practice this problem

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

Approach Overview

Problem Overview: You get a sorted array that has been rotated at an unknown pivot. The order is still increasing on each side of the pivot. Your task is to find the index of a target value in O(log n) time. If the target does not exist, return -1.

Approach 1: Linear Scan (O(n) time, O(1) space)

The simplest approach is to iterate through the array and compare each element with the target. The moment you find a match, return its index. If the loop finishes without a match, return -1. This ignores the sorted property entirely and works for any array. While easy to implement, it runs in O(n) time, which fails the logarithmic time expectation usually implied in interview settings.

Approach 2: Binary Search with Rotation Logic (O(log n) time, O(1) space)

This approach modifies standard binary search. Even though the array is rotated, at least one half of the array remains sorted at any moment. Compute mid. If nums[mid] equals the target, return it immediately. Otherwise check whether the left half (nums[left]..nums[mid]) is sorted. If it is, verify whether the target lies inside that range and adjust right. If not, move left to the other half. If the right half is sorted, perform the symmetric check. This keeps halving the search space while respecting the rotation property.

Approach 3: Find Rotation Index then Binary Search (O(log n) time, O(1) space)

This method separates the problem into two steps. First, locate the rotation pivot using binary search. The pivot is the smallest element where the order breaks. Once you know the pivot, the array effectively becomes two sorted segments. Decide which segment could contain the target by comparing it with boundary values, then run a normal binary search on that half. This approach explicitly identifies the rotation structure, which some developers find easier to reason about when working with array transformations.

Recommended for interviews: The modified binary search with rotation logic is the expected solution. It keeps the implementation compact while maintaining O(log n) time. Explaining the linear scan briefly shows baseline reasoning, but demonstrating the rotated binary search proves you understand how sorted structure enables logarithmic search.

Approach 1: Binary Search with Rotation Logic

The essence of this approach is to perform a binary search with a twist, considering the rotation. We first determine which part of the array is sorted: the left or the right. This allows us to intelligently decide where to perform the binary search. If the target lies within the sorted side, we adjust the search range accordingly. Otherwise, we continue the search on the unsorted side, which in the next iteration becomes a new array.

This approach employs a standard binary search. The array is divided based on whether the left or the right half is sorted. If the left part is sorted, we check whether the target falls within that sorted range. If it does, the right boundary is adjusted; otherwise, the search continues in the right half, adjusting the left boundary, and vice versa for the right sorted half.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n) because each step reduces the search space by half.
Space Complexity: O(1) as no extra space is used aside from variables.

Try this approach in the editor →

Approach 2: Find Rotated Index and Execute Two Binary Searches

This decomposition-based approach first identifies the pivot index where rotation occurs. Once the break index is acquired, the target search bifurcates: running binary search on subarrays from the determined split point to either the beginning or end of the array.

This solution breaks the problem down by finding a rotation pivot index. The strategy shifts to standard binary search, applied twice on sub-sections of the array pre-determined by the pivot, thus achieving efficiency.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n) to find the pivot and additional O(log n) for binary search, leading to O(log n) overall.
Space Complexity: O(1) due to in-place operations.

Try this approach in the editor →

Approach 3: Binary Search

We use binary search to divide the array into two parts, [left,.. mid] and [mid + 1,.. right]. At this point, we can find that one part must be sorted.

Therefore, we can determine whether target is in this part based on the sorted part:

  • If the elements in the range [0,.. mid] form a sorted array:
    • If nums[0] leq target leq nums[mid], then our search range can be narrowed down to [left,.. mid];
    • Otherwise, search in [mid + 1,.. right];
  • If the elements in the range [mid + 1, n - 1] form a sorted array:
    • If nums[mid] \lt target leq nums[n - 1], then our search range can be narrowed down to [mid + 1,.. right];
    • Otherwise, search in [left,.. mid].

The termination condition for binary search is left geq right. If at the end we find that nums[left] is not equal to target, it means that there is no element with a value of target in the array, and we return -1. Otherwise, we return the index left.

The time complexity is O(log n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#PHP

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Binary Search with Rotation Logic

Time Complexity: O(log n) because each step reduces the search space by half.
Space Complexity: O(1) as no extra space is used aside from variables.

Find Rotated Index and Execute Two Binary Searches

Time Complexity: O(log n) to find the pivot and additional O(log n) for binary search, leading to O(log n) overall.
Space Complexity: O(1) due to in-place operations.

Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Linear ScanO(n)O(1)Quick brute-force check or when input size is very small
Binary Search with Rotation LogicO(log n)O(1)General optimal solution expected in coding interviews
Find Pivot then Binary SearchO(log n)O(1)Useful when you want a clear pivot-based reasoning for rotated arrays

Video Solution

Search in rotated sorted array - Leetcode 33 - Python • NeetCode • 543,851 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Search in Rotated Sorted Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Minimum in Rotated Sorted Array

Next

Pour Water Between Buckets to Make Water Levels Equal