Search in a rotated sorted list
Coding problemMediumAsked in: Adobe, Amazon, Flipkart, Google, Microsoft, Paytm
A list of distinct integers was sorted from smallest to largest and then rotated at an unknown point: for example [0, 1, 2, 4, 5, 6, 7] may have become [4, 5, 6, 7, 0, 1, 2]. It may also not be rotated at all. (Rotated means the front part of the list was moved to the back.)
Given such a list and a target, return the position of the target (counting from 0), or -1 if it is not there. Aim for O(log n) time.
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 = 1
Output: 0
Constraints
- The list holds between 0 and 100,000 integers
- Values are distinct and between -1,000,000,000 and 1,000,000,000
- The target is in the same range
Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.
Run your code to see the results here. Ctrl or Cmd + Enter runs; add Shift to submit.