DSA · Binary search · #15
Search in Rotated Sorted Array
Module 18 · difficulty 3/5·⏱ 30:00starts on first keystroke
An ascending sorted array `nums` (distinct values) is possibly rotated at an unknown pivot. Given `nums` and a `target`, return the index of `target` if it is in the array, or `-1` if it is not. You must write an algorithm with O(log n) runtime.
Examples
nums = [4,5,6,7,0,1,2], target = 0→4nums = [4,5,6,7,0,1,2], target = 3→-1nums = [1], target = 0→-1
Constraints
- · 1 <= nums.length <= 5000
- · -10^4 <= nums[i] <= 10^4
- · All values of nums are unique.
- · nums is an ascending array possibly rotated.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.