Implement Sorting or Searching | Dataford Interview Questions

CustomerInsights.AI stores distinct customer engagement scores in ascending order, but a synchronization boundary may rotate the array. Given the rotated array and a target score, return the target's index or -1 if it is absent.

You must solve the problem with a modified binary search. The array contains distinct values, so at every iteration at least one half remains sorted.

Formal Specification

Implement search_rotated(nums, target).

Input: nums, a list of distinct integers formed by rotating an ascending list, and target, an integer.
Output: The zero-based index of target in nums, or -1 when it does not occur.
A rotation of zero positions is valid, so the input may already be sorted.

Constraints

1 <= len(nums) <= 10^5
-10^9 <= nums[i], target <= 10^9
All values in nums are distinct
nums is a rotation of an ascending array

Function Signature

def search_rotated(nums, target):

Your question is Implement Sorting or Searching. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem