A large-scale platform stores sorted datasets such as:
- user activity logs
- product rankings
- time-series data
Due to system optimizations like caching or load balancing, the sorted array is sometimes rotated at an unknown pivot.
For example:
Original: [0,1,2,4,5,6,7]
Rotated: [4,5,6,7,0,1,2]
Despite the rotation, the system must still perform efficient lookups.
A linear search would take O(n) time, which is inefficient. The system expects a solution using modified Binary Search in O(log n) time.
This is a very common interview problem asked in Google, Amazon, Microsoft, Meta, and other top companies.
Your Task
Given:
- a rotated sorted array
nums (no duplicate elements) - an integer
target
👉 Return the index of target if it exists
👉 Otherwise, return -1
Input Format
nums: rotated sorted arraytarget: integer
Output Format
- Integer index of target, or
-1
Examples
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3:
Input: nums = [1], target = 0
Output: -1