Modified Binary Search
LC #33Medium
Search in Rotated Sorted Array
Modified Binary Search
AmazonGoogleMetaBloombergMicrosoftProblem
Search a target in a sorted array that has been rotated at some unknown pivot.
arraybinary-search
Constraints
- ›1 ≤ n ≤ 5000
- ›-10⁴ ≤ nums[i] ≤ 10⁴
- ›All values are unique
- ›O(log n) runtime required
Example
Input
nums = [4, 5, 6, 7, 0, 1, 2], target = 0Output
4Why
Array rotated at pivot index 4. 0 is at index 4