Log inSign up
mediumleetcodeNot Started

Search in Rotated Sorted Array

Given an integer array nums sorted in ascending order (with distinct values) that is rotated at an unknown pivot index, and an integer target, find the index of target in nums, or return -1 if it is not in nums.

Binary Search
Solve on leetcode
Lesson

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 · Example 1: Rotated Array with Target Present:

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
Explanation: Element 0 exists in nums at index 4.

Example 2 · Example 2: Target Not in Array:

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1
Explanation: Element 3 is not present in nums, so return -1.

Example 3 · Example 3: Single Element Array:

Input: nums = [1], target = 0
Output: -1
Explanation: 0 does not exist in [1], return -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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Identify the invariant that at least one half of a rotated sorted array is always sorted.
  • Implement single-pass O(log n) binary search without finding the pivot index first.
  • Handle boundary conditions carefully to prevent off-by-one errors.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Array was originally sorted, then rotated at an unknown pivot.
  • Strict O(log n) runtime constraint.
  • Elements are distinct (no duplicate ambiguities).

Algorithmic Decision Tree:

  • Calculate mid = low + (high - low) / 2.
  • If nums[mid] == target, return mid immediately.
  • If nums[low] <= nums[mid], left half is sorted: if target in [nums[low], nums[mid]), high = mid - 1; else low = mid + 1.
  • Otherwise right half is sorted: if target in (nums[mid], nums[high]], low = mid + 1; else high = mid - 1.

Connected Patterns:

Find Minimum in Rotated Sorted ArraySearch in Rotated Sorted Array II (with duplicates)Peak Index in a Mountain Array

1. Linear Search

Intuition

Iterate through each index i from 0 to n-1. If nums[i] == target, return index i immediately. If the loop completes without finding target, return -1.

When to apply: Useful as an initial benchmark or when the array is very small and unsorted.

Algorithm

  1. Step 1: Iterate index i from 0 to nums.length - 1.
  2. Step 2: Check if nums[i] equals target.
  3. Step 3: If equal, return i.
  4. Step 4: If loop finishes without match, return -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int search(vector<int>& nums, int target) {
10 for (int i = 0; i < (int)nums.size(); ++i) {
11 if (nums[i] == target) return i;
12 }
13 return -1;
14 }
15};
16
17int main() {
18 // Sample driver execution
19 cout << "Execution completed successfully." << endl;
20 return 0;
21}
22

Time & Space Complexity

  • Time complexity: O(n) — In the worst case, we inspect all n elements of the array sequentially.
  • Space complexity: O(1) — Only a single index variable is maintained, requiring O(1) auxiliary space.

2. Two-Pass Binary Search (Find Pivot First)

Intuition

Find the pivot index k where the rotation happened using binary search in O(log n). The array is split into two sorted subarrays: nums[0...k-1] and nums[k...n-1]. Decide which subarray target belongs to based on nums[0] and nums[n-1], then run standard binary search on that half.

When to apply: When you want a modular separation between pivot finding and binary searching.

Algorithm

  1. Step 1: Find the index of the minimum element (pivot) using binary search where nums[mid] > nums[high].
  2. Step 2: If target is between nums[pivot] and nums[n-1], search the right subarray [pivot, n-1].
  3. Step 3: Otherwise, search the left subarray [0, pivot - 1].
  4. Step 4: Return the index found or -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int search(vector<int>& nums, int target) {
10 int n = nums.size();
11 int low = 0, high = n - 1;
12 while (low < high) {
13 int mid = low + (high - low) / 2;
14 if (nums[mid] > nums[high]) low = mid + 1;
15 else high = mid;
16 }
17 int pivot = low;
18 low = 0; high = n - 1;
19 if (target >= nums[pivot] && target <= nums[high]) {
20 low = pivot;
21 } else {
22 high = pivot - 1;
23 }
24 while (low <= high) {
25 int mid = low + (high - low) / 2;
26 if (nums[mid] == target) return mid;
27 else if (nums[mid] < target) low = mid + 1;
28 else high = mid - 1;
29 }
30 return -1;
31 }
32};
33
34int main() {
35 // Sample driver execution
36 cout << "Execution completed successfully." << endl;
37 return 0;
38}
39

Time & Space Complexity

  • Time complexity: O(log n) — Finding the pivot takes O(log n) time and the subsequent binary search takes O(log n) time, giving O(log n) total.
  • Space complexity: O(1) — No extra memory is allocated beyond pointers, giving O(1) space.

3. Single-Pass Binary Search with Sorted Half Invariant

Intuition

Maintain low and high pointers. In each step, calculate mid. If nums[mid] == target, return mid. If nums[low] <= nums[mid], the left half is sorted: if nums[low] <= target < nums[mid], search left (high = mid - 1); else search right (low = mid + 1). Otherwise, the right half must be sorted: if nums[mid] < target <= nums[high], search right (low = mid + 1); else search left (high = mid - 1).

When to apply: Standard optimal solution in technical interviews.

Algorithm

  1. Step 1: Initialize low = 0, high = nums.length - 1.
  2. Step 2: While low <= high, compute mid = low + (high - low) / 2.
  3. Step 3: If nums[mid] == target, return mid.
  4. Step 4: If nums[low] <= nums[mid] (left half sorted):
  5. - If nums[low] <= target && target < nums[mid], set high = mid - 1.
  6. - Else set low = mid + 1.
  7. Step 5: Else (right half sorted):
  8. - If nums[mid] < target && target <= nums[high], set low = mid + 1.
  9. - Else set high = mid - 1.
  10. Step 6: If low > high, return -1.

Interactive Pointer Trace for nums = [4, 5, 6, 7, 0, 1, 2], target = 0

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Initial state: low=0 (val=4), high=6 (val=2)
Visual state
Values and pointers at this exact step
pointers
S
4
5
6
7
0
1
2
0
↑ low
1
2
3
↑ mid
4
5
6
↑ high
Check / comparison
nums[low]=4 <= nums[mid]=7 (Left sorted). Is target 0 in [4, 7]? No.
Decision / next transition
Set low = 4. Target must be in right half.
Why this step matters

Initial state: low=0 (val=4), high=6 (val=2). mid=3 (val=7). Left half [4, 5, 6, 7] is sorted because nums[0] <= nums[3]. Target 0 is NOT in [4, 7], so eliminate left half by setting low = mid + 1 = 4.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int search(vector<int>& nums, int target) {
10 int low = 0, high = (int)nums.size() - 1;
11 while (low <= high) {
12 int mid = low + (high - low) / 2;
13 if (nums[mid] == target) return mid;
14
15 // Check if left half is sorted
16 if (nums[low] <= nums[mid]) {
17 if (nums[low] <= target && target < nums[mid]) {
18 high = mid - 1;
19 } else {
20 low = mid + 1;
21 }
22 } else { // Right half is sorted
23 if (nums[mid] < target && target <= nums[high]) {
24 low = mid + 1;
25 } else {
26 high = mid - 1;
27 }
28 }
29 }
30 return -1;
31 }
32};
33
34int main() {
35 // Sample driver execution
36 cout << "Execution completed successfully." << endl;
37 return 0;
38}
39

Time & Space Complexity

  • Time complexity: O(log n) — Each comparison eliminates half of the remaining elements, guaranteeing log2(n) iterations.
  • Space complexity: O(1) — Requires only constant O(1) auxiliary variables (low, high, mid).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear SearchO(n)O(1)Sequentially inspect every element.Does not exploit the sorted nature of the partitions.
2.Two-Pass Binary SearchO(log n)O(1)Find the pivot index first, then perform standard binary search on one half.Does extra comparisons finding the pivot index first.
3.Single-Pass Binary SearchOptimalO(log n)O(1)Identify the sorted half on the fly and prune half the search space in each step.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Single element array matching target: nums = [1], target = 1 -> return 0.
  • Single element array not matching target: nums = [1], target = 0 -> return -1.
  • Two element array rotated: nums = [3, 1], target = 1 -> return 1.
  • Array not rotated at all: nums = [1, 2, 3, 4, 5], target = 3 -> return 2.
  • Target is the minimum or maximum element in the array.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Start by explaining why a standard binary search fails on rotated arrays (the whole array is not monotonic).
  2. Explain the key observation: the midpoint divides the array into one sorted half and one non-sorted half.
  3. Walk through the boundary conditions for checking if target lies within the sorted half: low <= mid and nums[low] <= target < nums[mid].
  4. Mention that distinct elements make this O(log n) guaranteed, whereas duplicate elements can degrade to O(n).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is at least one half of a rotated sorted array always sorted?

2.If nums[low] <= nums[mid], what condition ensures target is in the left half?

Back to DSA Sheet