Search in a rotated sorted array
Python data engineering interview problem. Difficulty: intermediate. Pattern: Binary Search. About 16 minutes. Part of the Pro drill bank.
Find a value in an ascending list that was rotated at an unknown pivot. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.
An index can be sorted except for one rotation point, so a normal full scan wastes the structure that is still available. Find target in a rotated ascending array of distinct values and return its index, or -1 if it is absent. Keep logarithmic work. Write search_rotated(nums: list[int], target: int) -> int. In [4,5,6,7,0,1,2], target 0 is at index 4. The starter file already contains the function name, harness and print lines. Keep them and fill only the function body.
Requirements
- Discard half the search range at each step.
- Identify which half is normally sorted.
- Return -1 when target is not present.
Constraints
- Values are distinct and the list came from one rotation of ascending order.
- The return type is int and expected time is O(log n).
Examples
Input: search_rotated([4, 5, 6, 7, 0, 1, 2], 0) Output: 4 0 sits at index 4, after the rotation point.
Topics: lakebench, python, rotated, sorted, log n.
More Python interview questions · All interview problems · Learn data engineering
Search in a rotated sorted array
Interview-style drill: Find a value in an ascending list that was rotated at an unknown pivot.
Implement `search_rotated(nums: list[int], target: int) -> int`. `nums` held distinct values in ascending order, then was rotated at some pivot: `[0, 1, 2, 4, 5, 6, 7]` may have become `[4, 5, 6, 7, 0, 1, 2]`. Return the index of `target`, or `-1` if it is not there. The list can hold 100,000 elements, so the work should grow with the logarithm of its length.