Find it in a turned list
A list of different whole numbers was sorted in increasing order, then turned: some number of values were taken off the front and put back at the end, in order. That list is nums. For example [2, 5, 9, 12, 15, 18] could become [15, 18, 2, 5, 9, 12].
Return the position of target in nums, or -1 if it is not there. Aim for O(log n) time.
- Input
nums = [15,18,2,5,9,12]
target = 5- Output
3
5 sits at position 3.
- Input
nums = [15,18,2,5,9,12]
target = 7- Output
-1
7 is not in the list.
- Input
nums = [4]
target = 4- Output
0
A list of one.
Limits
1 <= nums.length <= 100000-10^9 <= nums[i], target <= 10^9All values in nums are different.
Hints
Hint 1
Split the list in the middle: at least one half is in plain sorted order.
Hint 2
Check whether the target falls inside the sorted half; if not, look in the other one.
Where this was reported
- Qualcomm, On-campus interview, 2023 (GeeksforGeeks)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
