DSA · Binary Search · #159
Search in Rotated Sorted Array
Module 59 · difficulty 3/5·⏱ 30:00starts on first keystroke
There is an integer array `nums` sorted in ascending order with **distinct** values. Before being passed to your function, `nums` is possibly rotated at an unknown pivot index `k` (`0 <= k < nums.length`), so it becomes `[nums[k], nums[k+1], ..., nums[n-1], nums[0], ..., nums[k-1]]`. Implement `search(nums, target)` that returns the **index** of `target` if it is in `nums`, or `-1` if it is not. You must write an algorithm with `O(log n)` runtime complexity.
Examples
nums = [4,5,6,7,0,1,2], target = 0→4— 0 sits at index 4 after rotation.nums = [4,5,6,7,0,1,2], target = 3→-1— 3 is absent.nums = [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 that is possibly rotated.
- · -10^4 <= target <= 10^4
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.