IntermediateArrays
Search in Rotated Sorted Array
Problem
An ascending sorted array of distinct integers has been rotated at some unknown pivot, so [0,1,2,4,5,6,7] may become [4,5,6,7,0,1,2]. Given the rotated array nums and a target, return the index of target or -1 if it is not present. Your algorithm must run in O(log n) time.
Constraints
- 1 ≤ n ≤ 5·10^3
- -10^4 ≤ nums[i], target ≤ 10^4
- all values are distinct
- rotation offset is unknown and may be 0
Examples
in: nums = [4,5,6,7,0,1,2], target = 0
out: 4
in: nums = [4,5,6,7,0,1,2], target = 3
out: -1
What this tests
- Adapting binary search when the global order is broken
- Using the invariant "at least one half is sorted"
- Careful inequality reasoning (which half to discard)
- Off-by-one and loop-termination discipline
- Understanding the impact of duplicates
Systematic ReasoningImplementationEdge CasesComplexity AnalysisPattern Recognition
Progressive hints
Choose how much help you want. Each hint reveals a little more; the pattern is not named until hint 2.
Hint 1Direction
Hint 2Pattern
Hint 3Data structure
Hint 4Algorithm
Hint 5Pseudocode
Solution
Solve in your language
The editor, starter code and solution adapt to the language you pick — C++, JavaScript, TypeScript or Python.
Solve in
Candidate thinking
How a strong candidate reasons through this problem, step by step.
Try the problem yourself first (or run the mock interview), then compare your process against a strong candidate's.
Follow-up engine
Requirements change; so does the right algorithm.
F1
The array may contain duplicates. What changes?
F2
Find the minimum element (the rotation point) instead.
F3
Now the array is rotated *and* you must support point updates between queries.
F4
Generalise: search a sorted array of unknown length (you only have
get(i) that throws out of bounds).