33. Search in Rotated Sorted Array
Asked at Google, Meta, Oracle, Salesforce and 5 more
Difficulty
Medium
Time
O(log n)
Space
O(1)
Pattern
Array
Companies
9
Problem
You are given an integer array nums that was sorted in ascending order, then rotated at some unknown pivot. Rotating means some prefix was cut off and moved to the back, so the array looks like two sorted runs: a larger run followed by a smaller run. All values in nums are distinct.
Given a target value, return the index where target appears in nums, or -1 if it is not there.
Your algorithm must run in O(log n) time, so a plain linear scan is not good enough. The trick is that even after rotation, at least one half of any range you look at is still fully sorted — you can use that to decide which half to keep searching.
A sorted array that was rotated
Constraints
- ●
1 <= nums.length <= 5000 - ●
-10^4 <= nums[i] <= 10^4 - ●
All values of nums are unique. - ●
nums is an ascending array that is possibly rotated. - ●
-10^4 <= target <= 10^4
Examples
nums = [4,5,6,7,0,1,2], target = 04nums = [4,5,6,7,0,1,2], target = 3-1nums = [1], target = 0-1Asked At
9 companies| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Oracle | Medium | View all Oracle questions → |
| Salesforce | Medium | View all Salesforce questions → |
| Walmart | Medium | View all Walmart questions → |
| Bloomberg | Medium | View all Bloomberg questions → |
| Goldman Sachs | Medium | View all Goldman Sachs questions → |
| TikTok | Medium | View all TikTok questions → |
| Medium | View all LinkedIn questions → |
How to Think About It
The array is rotated, but at least one half is always sorted. Use that property to decide which half to search.
Compare nums[mid] with nums[left]. If nums[left] <= nums[mid], the left half is sorted. Otherwise the right half is sorted.
If the left half is sorted: check if target is in [nums[left], nums[mid]). If yes, search left. If no, search right.
If the right half is sorted: check if target is in (nums[mid], nums[right]]. If yes, search right. If no, search left.
Edge cases: target not found (return -1), single element (return 0 or -1), target at pivot point.
Optimal Approach
Binary search with a twist:
Step 1: Find mid = (lo + hi) // 2.
Step 2: If nums[mid] == target, return mid.
Step 3: Determine which half is sorted:
- If nums[lo] <= nums[mid]: left half is sorted
- Else: right half is sorted
Step 4: Check if target is in the sorted half:
- Left sorted: if nums[lo] <= target < nums[mid], search left; else search right
- Right sorted: if nums[mid] < target <= nums[hi], search right; else search left
The key insight: in a rotated sorted array without duplicates, one half is always sorted. You can always determine which half by comparing nums[lo] and nums[mid].
Time: O(log n). Space: O(1).
Binary search: which half is sorted?
What Trips People Up in Real Interviews
Confusing this with binary search on a sorted array. The array is rotated, so you can't just check if target is between low and high. You need to determine which half is sorted.
Not handling the case where the target is in the unsorted half. Always check which half is sorted first, then determine if the target is in that half.
Forgetting that one half is always sorted. In a rotated sorted array, at least one of the two halves (left or right of mid) is guaranteed to be sorted.
Not handling duplicates. If the problem says duplicates are allowed, the approach changes (you can't always determine which half is sorted).
Using <= instead of < when checking which half is sorted. nums[lo] <= nums[mid] correctly identifies a sorted left half even when lo == mid. Using < breaks with 2-element arrays.
Solution Code
O(log n) timedef search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1Frequently Asked Questions
What is the Search in Rotated Sorted Array problem?
Given a sorted array that has been rotated at some pivot, find the index of a target value. The array has no duplicates. This problem tests your ability to modify binary search for a non-standard condition.
How do you solve Search in Rotated Sorted Array?
The optimal approach runs in O(log n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Search in Rotated Sorted Array?
Search in Rotated Sorted Array is asked at Google, Meta, Oracle, Salesforce, Walmart, Bloomberg, Goldman Sachs, TikTok, LinkedIn. It is a medium difficulty problem.
What are common mistakes on Search in Rotated Sorted Array?
- Confusing this with binary search on a sorted array. The array is rotated, so you can't just check if target is between low and high. You need to determine which half is sorted.
- Not handling the case where the target is in the unsorted half. Always check which half is sorted first, then determine if the target is in that half.
- Forgetting that one half is always sorted. In a rotated sorted array, at least one of the two halves (left or right of mid) is guaranteed to be sorted.
- Not handling duplicates. If the problem says duplicates are allowed, the approach changes (you can't always determine which half is sorted).
- Using <= instead of < when checking which half is sorted. `nums[lo]` <= `nums[mid]` correctly identifies a sorted left half even when lo == mid. Using < breaks with 2-element arrays.