The Rotated Array

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L5
Asked in
Palantir

Problem

A monitoring service keeps event IDs in ascending order, but a wraparound in its ring buffer means the export nums comes back rotated: the sequence climbs, drops exactly once at an unknown pivot, then climbs again, with no repeated values. Given that array and a target ID, return the index where target sits, or -1 when it is absent. The array can hold up to 100,000 IDs, so the lookup must stay logarithmic in its length.

Someone shuffled it. Now locate what you came for.

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

Worked solution and explanation

What this really is under the costume

Strip the ring-buffer wrapping and this is binary search with one extra question asked at every step: which side of mid is still in order? The data is sorted but cut once and the halves swapped, so the usual 'go left when the target is smaller' rule lies to you the moment you straddle the pivot. Candidates who reach for plain binary search pass the visible cases and then fail the instant the target sits on the far side of the break. The move that separates seniors: at each midpoint, decide which half is genuinely sorted, then test the target against that half's known bounds before committing a direction.

Break down the requirements

Step 1: Standard binary search setup

Initialize left = 0, right = len(nums) - 1.

Step 2: Determine which half is sorted

If nums[left] <= nums[mid], the left half is sorted. Otherwise the right half is sorted. The inclusive comparison matters: when left == mid, that single element is trivially sorted.

Step 3: Decide which half to search

If the target falls within the sorted half's value range, move into that half. Otherwise move into the other one.

Step 4: Return the index or -1

When nums[mid] == target, return mid. If the window collapses with no hit, return -1.

The solution

Binary search with sorted-half detection
def the_rotated_array(nums, target):
    left = 0
    right = len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Common follow-up questions