Search in Rotated Sorted Array is the #12 most asked LeetCode problem globally — the definitive test of whether you truly understand binary search beyond its textbook form.
Our analysis of 10,385 verified interview questions across 259 companies shows it appeared 68 times across 26 companies — including Google, Amazon, Meta, Microsoft, Goldman Sachs, Bloomberg, LinkedIn, ByteDance, and Arista Networks.
Standard binary search requires a fully sorted array. This problem gives you a sorted array that has been rotated — and still demands O(log n). The key insight: even in a rotated array, at least one half of any binary search window is always sorted. That's enough to make binary search work.
| Metric | Value |
|---|---|
| Total Interview Appearances | 68 verified mentions |
| Companies That Ask It | 26 companies |
| Global Rank | #12 out of 10,385 questions |
| Difficulty | Medium |
| Core Patterns | Array, Binary Search |
Google, Amazon, Meta, Microsoft, Goldman Sachs, Bloomberg, LinkedIn, ByteDance, Arista Networks, Adobe, Anduril, Apple, Autodesk, Criteo, Disney, Flipkart, Grammarly, Infosys, Media.net, MongoDB, and 6 more.
LeetCode #33 — Search in Rotated Sorted Array
There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed, nums is possibly rotated at an unknown pivot index. Given nums and an integer target, return the index of target if it exists, or -1.
Must run in O(log n) time.
Input: nums = [4,5,6,7,0,1,2], target = 0 → Output: 4
Input: nums = [4,5,6,7,0,1,2], target = 3 → Output: -1
Input: nums = [1], target = 0 → Output: -1In a rotated array, when you pick a midpoint, exactly one of the two halves (left or right of mid) is fully sorted. You can determine which one by comparing nums[left] with nums[mid].
nums[left] <= nums[mid] → left half is sorted. Check if target falls in [nums[left], nums[mid]]. If yes, search left. Else search right.nums[left] > nums[mid] → right half is sorted. Check if target falls in [nums[mid], nums[right]]. If yes, search right. Else search left.Identify the sorted half. Check if target is in the sorted half's range. If yes — search there. If no — search the other half. Repeat.
left=0, right=6, mid=3 → nums[mid]=7
nums[left]=4 <= nums[mid]=7 → left half [4,5,6,7] is sorted
target=0 not in [4,7] → search right: left=4
left=4, right=6, mid=5 → nums[mid]=1
nums[left]=0 <= nums[mid]=1 → left half [0,1] is sorted
target=0 in [0,1] → search left: right=4
left=4, right=4, mid=4 → nums[mid]=0 == target → return 4 ✅def search(nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# Left half is sorted
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1 # target in left half
else:
left = mid + 1 # target in right half
# Right half is sorted
else:
if nums[mid] < target <= nums[right]:
left = mid + 1 # target in right half
else:
right = mid - 1 # target in left half
return -1class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[left] <= nums[mid]) { // left half sorted
if (nums[left] <= target && target < nums[mid])
right = mid - 1;
else
left = mid + 1;
} else { // right half sorted
if (nums[mid] < target && target <= nums[right])
left = mid + 1;
else
right = mid - 1;
}
}
return -1;
}
}var search = function(nums, target) {
let left = 0, right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) return mid;
if (nums[left] <= nums[mid]) { // left half sorted
if (nums[left] <= target && target < nums[mid])
right = mid - 1;
else
left = mid + 1;
} else { // right half sorted
if (nums[mid] < target && target <= nums[right])
left = mid + 1;
else
right = mid - 1;
}
}
return -1;
};| Problem | Key Difference |
|---|---|
| LC #33 Search (distinct values) | Base problem — one half always sorted |
| LC #81 Search with Duplicates | When nums[left]==nums[mid], can't determine sorted half → shrink left |
| LC #153 Find Minimum | Find pivot — minimum is where sorted order breaks |
| LC #154 Find Min with Duplicates | Same, but handle nums[left]==nums[mid]==nums[right] edge case |
Tag on DSAPrep.dev under Binary Search.