Search in Rotated Sorted Array
Medium · Binary Search · Array · Binary Search
Problem
nums was sorted ascending with distinct values, then rotated left at some unknown pivot — so [0,1,2,4,5,6,7] might arrive as [4,5,6,7,0,1,2].
Return the index of target, or -1. Your solution must run in O(log n).
Examples
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
Not present.
Input: nums = [1], target = 0 Output: -1
Constraints
- 1 <= len(nums) <= 5000
- -10^4 <= nums[i], target <= 10^4
- All values are distinct
- nums is a rotation of a sorted array
Approaches
- Find the pivot, then search one run — time O(log n), space O(1)
Related problems
Start free on Cariara · Coding problems · System design studio
