Search in Rotated Sorted Array — Medium Coding Interview Question

Search for a target in a rotated sorted array. The array was sorted then rotated at an unknown pivot. Must be O(log n).

Example

Input: nums = [4,5,6,7,0,1,2], target = 0

Output: 4

Constraints

• 1 ≤ nums.length ≤ 5000
• All values are unique.

Topics & Companies

Topics: binary-search, arrays

Asked by: Amazon, Google, Meta, Microsoft, Apple, Bloomberg, Uber

Optimal Solution Complexity

Time complexity: O(log n). Space complexity: O(1).

Practice more

• All DSA Problems
• DSA Patterns