Search in Rotated Sorted Array — The Binary Search Problem Every FAANG Interviewer Loves
Sanjeev SharmaAdvertisement
Problem Statement
Given an integer array
numssorted in ascending order (with distinct values) that has been rotated at an unknown pivot indexk, and atargetvalue, return the index oftargetinnums, or-1if it is not present.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^4 <= nums[i] <= 10^4- All values in
numsare unique numsis an ascending array rotated at some pivot-10^4 <= target <= 10^4
- Why This Problem Matters
- The Core Observation
- The Decision Tree
- Step-by-Step Algorithm (Pseudocode)
- Visual Dry Run
- Common Mistakes
- Mistake 1: Using < instead of <= to identify the sorted half
- Mistake 2: Not including the boundary values in the range check
- Mistake 3: Forgetting the non-rotated case
- Mistake 4: Moving to mid instead of mid ± 1
- Solutions
- Python
- JavaScript
- Complexity Analysis
- Follow-Up Questions
- LC 81 — Search in Rotated Sorted Array II (with duplicates)
- LC 153 — Find Minimum in Rotated Sorted Array
- LC 154 — Find Minimum in Rotated Sorted Array II (with duplicates)
- Find the Rotation Index Itself
- How Interviewers Probe Your Understanding
- This Pattern Solves
- Key Takeaway
Why This Problem Matters
LeetCode 33 is not just a medium-difficulty problem — it is one of the most reliably asked binary search questions across Google, Meta, Amazon, and Microsoft interviews. A search of interview reports on Blind, Glassdoor, and LeetCode discussion threads repeatedly surfaces this problem under real interview conditions.
The reason it appears so often is not because it is tricky for its own sake. It is because this problem exposes whether a candidate truly understands binary search at a conceptual level, or whether they have only memorized the template.
Standard binary search works because the array is sorted, and being sorted means you can make a binary decision at the midpoint: the target is either in the left half or the right half, and you can tell which with a single comparison. The moment you rotate the array, that direct comparison breaks — nums[mid] no longer tells you which direction to move in an obvious way.
To recover O(log n), you need to discover a new invariant that still lets you throw away half the search space at each step. That invariant is the subject of this entire article, and understanding it deeply is what separates candidates who solve this cleanly from those who fumble through it.
Interviewers also love this problem because it opens natural doors to follow-up questions: What if there are duplicates? What if you need the rotation index itself? What if the matrix is 2D? Candidates who truly understand the invariant can answer these extensions on the fly. Those who have memorized code cannot.
The Core Observation
Before writing a single line of code, pause and think about what rotation actually does to an array.
Start with a fully sorted array: [0, 1, 2, 4, 5, 6, 7]
Rotate it at index 3 (shift the first three elements to the end): [4, 5, 6, 7, 0, 1, 2]
Now pick the midpoint: mid = 3, so nums[mid] = 7.
Look at the left half: [4, 5, 6, 7]. This is perfectly sorted. Look at the right half: [7, 0, 1, 2]. This contains the rotation point — it is not sorted.
Now try a different pivot. Rotate the original array at index 5: [6, 7, 0, 1, 2, 4, 5]
Midpoint: mid = 3, nums[mid] = 1.
Left half: [6, 7, 0, 1]. Contains the rotation point — not sorted. Right half: [1, 2, 4, 5]. Perfectly sorted.
Notice the pattern? The rotation point can only exist in one half at a time. The pivot is a single break in the ordering. When you split the array at any midpoint, that break lands in exactly one of the two halves. The other half has no break — it is entirely sorted.
This is the invariant: at every step of binary search on a rotated sorted array, at least one half is always fully sorted.
It does not matter where the pivot is. It does not matter how many times the array has been rotated conceptually. As long as there are distinct values and a single rotation point, splitting at any midpoint always guarantees one sorted half.
This is the key that unlocks everything.
The Decision Tree
Once you know that one half is always sorted, the algorithm becomes clear. Here is the decision logic written out as a tree:
Compute mid = (left + right) / 2
If nums[mid] == target → return mid (done)
Check which half is sorted:
IF nums[left] <= nums[mid]:
→ The LEFT half [left..mid] is sorted
Check if target falls in this sorted range:
IF nums[left] <= target < nums[mid]:
→ Target could be here → search LEFT (right = mid - 1)
ELSE:
→ Target is NOT in left half → search RIGHT (left = mid + 1)
ELSE:
→ The RIGHT half [mid..right] is sorted
Check if target falls in this sorted range:
IF nums[mid] < target <= nums[right]:
→ Target could be here → search RIGHT (left = mid + 1)
ELSE:
→ Target is NOT in right half → search LEFT (right = mid - 1)
If left > right → return -1 (not found)
The critical insight is this: you are not searching the sorted half because it is sorted. You are using the sorted half to eliminate it or the other half. In a sorted subarray, you can check membership with two comparisons. If the target cannot be in the sorted half (because it falls outside the range), it must be in the other half — and you search there instead.
This is fundamentally different from standard binary search. You are always moving toward the answer, but the evidence you use to make the move is "which half is sorted" rather than "is the target bigger or smaller than mid."
Step-by-Step Algorithm (Pseudocode)
function search(nums, target):
left = 0
right = len(nums) - 1
while left <= right:
mid = left + (right - left) / 2 # avoids integer overflow
if nums[mid] == target:
return mid
# Determine which half is sorted
if nums[left] <= nums[mid]: # left half is sorted
if nums[left] <= target < nums[mid]:
right = mid - 1 # search left half
else:
left = mid + 1 # search right half
else: # right half is sorted
if nums[mid] < target <= nums[right]:
left = mid + 1 # search right half
else:
right = mid - 1 # search left half
return -1 # target not found
Why nums[left] <= nums[mid] and not <?
When left == mid (array of size 1 or 2), nums[left] == nums[mid] and the left half is trivially "sorted" (it contains just one element). Using <= correctly handles this edge case. Using < would misclassify it and cause incorrect behavior.
Why nums[left] <= target < nums[mid] (strict < on the right)?
Because nums[mid] has already been checked and ruled out. We need the target to be strictly less than nums[mid] to place it in the left half.
Visual Dry Run
Let us trace through nums = [4, 5, 6, 7, 0, 1, 2], target = 0 step by step.
Initial state:
Index: 0 1 2 3 4 5 6
Array: [4, 5, 6, 7, 0, 1, 2]
left=0, right=6
Iteration 1:
mid = (0 + 6) / 2 = 3
nums[mid] = nums[3] = 7
Is 7 == 0? No.
Is nums[left] <= nums[mid]? → nums[0]=4 <= nums[3]=7 → YES
→ LEFT half [4, 5, 6, 7] is sorted
Is target in left half range? → 4 <= 0 < 7? → NO (0 < 4)
→ Target NOT in left half → search RIGHT
→ left = mid + 1 = 4
State after iteration 1: left=4, right=6
Iteration 2:
mid = (4 + 6) / 2 = 5
nums[mid] = nums[5] = 1
Is 1 == 0? No.
Is nums[left] <= nums[mid]? → nums[4]=0 <= nums[5]=1 → YES
→ LEFT half [0, 1] is sorted
Is target in left half range? → 0 <= 0 < 1? → YES
→ Target could be in left half → search LEFT
→ right = mid - 1 = 4
State after iteration 2: left=4, right=4
Iteration 3:
mid = (4 + 4) / 2 = 4
nums[mid] = nums[4] = 0
Is 0 == 0? YES → return 4
Result: index 4. Correct.
The algorithm made only 3 iterations on a 7-element array. No wasted comparisons. Every step either found the target or eliminated half the remaining search space.
Common Mistakes
Mistake 1: Using < instead of <= to identify the sorted half
# WRONG
if nums[left] < nums[mid]:
# CORRECT
if nums[left] <= nums[mid]:
When left == mid (which happens when the window shrinks to two elements), nums[left] == nums[mid]. If you use strict <, you fall into the else branch and treat the right half as sorted — even though the left half actually contains just the single element at left=mid. This can push left in the wrong direction.
Mistake 2: Not including the boundary values in the range check
# WRONG — misses the case where target == nums[left]
if nums[left] < target < nums[mid]:
# CORRECT
if nums[left] <= target < nums[mid]:
The sorted left half includes nums[left] itself. If target equals nums[left], it belongs to the left half. Similarly for the right half, nums[right] is included.
Mistake 3: Forgetting the non-rotated case
An array that has never been rotated — or has been rotated by exactly n positions — is simply a sorted array. Your code must handle nums = [1, 2, 3, 4, 5] without rotation. If you write nums[left] <= nums[mid], the non-rotated case naturally satisfies this condition (the entire left half is sorted), and the algorithm degrades gracefully to standard binary search. Do not add special-case logic for this — it is handled implicitly.
Mistake 4: Moving to mid instead of mid ± 1
# WRONG — causes infinite loop when left == mid
right = mid
# CORRECT
right = mid - 1
Once you have ruled out nums[mid] as the target, never include it in the next search window. Setting right = mid instead of right = mid - 1 can trap the loop when left == mid, oscillating forever without making progress.
Solutions
Python
class Solution:
def search(self, nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2 # safe midpoint (no overflow)
if nums[mid] == target:
return mid
# Determine which half is sorted by comparing left boundary to mid
if nums[left] <= nums[mid]:
# Left half [left..mid] is fully sorted
if nums[left] <= target < nums[mid]:
# Target falls within the sorted left range
right = mid - 1
else:
# Target is outside left range; must be in right half
left = mid + 1
else:
# Right half [mid..right] is fully sorted
if nums[mid] < target <= nums[right]:
# Target falls within the sorted right range
left = mid + 1
else:
# Target is outside right range; must be in left half
right = mid - 1
return -1 # target not found
JavaScript
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
function search(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
// Compute midpoint safely to avoid integer overflow
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) {
return mid;
}
// Check which half is sorted
if (nums[left] <= nums[mid]) {
// Left half [left..mid] is fully sorted
if (nums[left] <= target && target < nums[mid]) {
// Target is within the sorted left half
right = mid - 1;
} else {
// Target is not in the left half; search right
left = mid + 1;
}
} else {
// Right half [mid..right] is fully sorted
if (nums[mid] < target && target <= nums[right]) {
// Target is within the sorted right half
left = mid + 1;
} else {
// Target is not in the right half; search left
right = mid - 1;
}
}
}
return -1; // target not found
}
Both solutions are clean, well-commented, and follow the same logic. The only language-specific detail is using Math.floor in JavaScript (since / does not truncate integers) and // for integer division in Python.
Complexity Analysis
| Metric | Value | Reason |
|---|---|---|
| Time | O(log n) | Each iteration halves the search space; at most log₂(n) iterations |
| Space | O(1) | Only constant extra variables (left, right, mid) |
The O(log n) guarantee holds because we always eliminate at least half the remaining array at each step, regardless of where the rotation point falls. This matches the constraint stated in the problem.
Follow-Up Questions
LC 81 — Search in Rotated Sorted Array II (with duplicates)
The problem becomes significantly harder when duplicates are allowed. Consider the array [1, 3, 1, 1, 1] and target 3. When nums[left] == nums[mid] == nums[right], you cannot determine which half is sorted. You have no way to know if you are in the left plateau or the right one.
The fix: when nums[left] == nums[mid] == nums[right], increment left and decrement right by one and try again. This safely shrinks the window, but in the worst case (e.g., [1,1,1,1,1,1,1] searching for 2), you shrink by only one element per iteration.
Worst-case time complexity degrades to O(n). This is a fundamental mathematical limit when duplicates obscure the sorted half — you have no choice but to check each element individually in that worst case.
LC 153 — Find Minimum in Rotated Sorted Array
Instead of searching for a target, find the minimum element. The same "one half is always sorted" insight applies. The minimum is always at the start of the unsorted half. When nums[mid] > nums[right], the minimum is in the right half. Otherwise, it is in the left half (and nums[mid] could itself be the minimum, so use right = mid, not right = mid - 1).
LC 154 — Find Minimum in Rotated Sorted Array II (with duplicates)
Same as LC 153 but with duplicates. Same problem as LC 81: when nums[mid] == nums[right], you cannot determine which half contains the minimum, so you decrement right by one. Worst case degrades to O(n) again.
Find the Rotation Index Itself
This is essentially LC 153. The rotation index is the index of the minimum element. Once found, you know the full structure of the array and can perform two independent standard binary searches (one on each sorted subarray).
How Interviewers Probe Your Understanding
Expect these questions after you present your solution:
"What if the array has duplicates?" — This tests whether you understand why your current key comparison (
nums[left] <= nums[mid]) breaks with duplicates. The correct answer involves acknowledging the worst-case O(n) degradation."Why
<=instead of<when checking the sorted half?" — This directly tests your understanding of the edge case whereleft == mid."Can you solve it without the
<=in the range check on the right boundary?" — Pushes you to reason about whether the strict inequality is strictly necessary."What happens if the entire array is non-rotated?" — Tests that your solution handles the identity rotation gracefully without special casing.
"What is the loop invariant?" — The invariant is: if
targetexists innums, it exists innums[left..right]. The loop preserves this invariant at every step.
This Pattern Solves
The "identify the sorted half" pattern generalizes well beyond this single problem:
- Find Peak Element (LC 162) — use a similar "which side is ascending" comparison to binary search for the peak
- Search a 2D Matrix (LC 74, LC 240) — structured binary elimination on non-flat sorted structures
- Find in Mountain Array (LC 1095) — binary search for the peak first, then binary search each side
- Koko Eating Bananas (LC 875) / Capacity to Ship Packages (LC 1011) — binary search on answer space rather than array contents, but the same "eliminate half the space per step" discipline
Any time you need O(log n) on a structure that is not perfectly sorted but has a local sorted guarantee, this family of techniques applies.
Key Takeaway
The insight that unlocks this problem — one half of the array is always sorted after any rotation — is what separates a clean O(log n) solution from a confused O(n) attempt. Once you internalize that a single rotation point can only break ordering in one half at a time, the algorithm writes itself: identify the sorted half, use range checks to determine where the target must be, and eliminate the impossible half. Every follow-up in this family (duplicates, finding the minimum, finding the rotation point) is simply a variation of the same core invariant, and mastering this one problem gives you the mental model to solve all of them without rememorizing new code.
Advertisement
