The Silent Locator

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

Domain
Python
Difficulty
easy
Seniority
L3
Asked in
Houzz

Problem

A read cache keeps record IDs in ascending order, but a maintenance job rotated the sequence at an unknown point, moving a block from the front to the back so the IDs now climb, wrap once, then climb again. Given this rotated arr of distinct IDs and a target, return the position of target, or -1 if it is absent, and keep the lookup logarithmic in the size of arr.

Every lookup should cost you less than the one before it.

Example 1

Input:

arr = [4,5,6,7,0,1,2], target = 0

Output:

4

Example 2

Input:

arr = [4,5,6,7,0,1,2], target = 6

Output:

2

Worked solution and explanation

What this problem really is

This is a binary search over a rotated sorted array wearing a cache-lookup costume. The IDs climb, wrap once at an unknown pivot, then climb again, and that single wrap is the entire problem. The reflex move is to reach for bisect, or to compare arr[mid] to the target like an ordinary binary search. Both break: bisect assumes global ascending order and lands on the wrong side of the pivot, and a bare arr[mid] comparison cannot tell which half of a rotated window is actually in order. Guess wrong about which half holds the target and you prune away the half that contains it, so the ID comes back missing even though it is sitting right there. And target in arr finds it but scans every row, blowing the logarithmic budget the moment the cache holds millions of IDs.

Building it step by step

Step 1: Bracket the whole range

Set low = 0 and high = len(arr) - 1 so the window spans the whole rotated list. On an empty list high starts at -1, the loop never runs, and you get the correct not-found path for free.

Step 2: Find the sorted half

Compute mid = (low + high) // 2. If arr[mid] == target, return mid. Otherwise decide which side is ordered: if arr[low] <= arr[mid], the left side from low to mid is sorted; if not, the pivot is on the left and the right side from mid to high is the sorted one.

Step 3: Decide which half to keep

When the left is sorted, the target belongs there only if arr[low] <= target < arr[mid], so set high = mid - 1; otherwise low = mid + 1. Mirror it when the right is sorted: if arr[mid] < target <= arr[high], set low = mid + 1, else high = mid - 1. The plus/minus one keeps the window strictly shrinking so the loop cannot hang.

Step 4: Fall through to not-found

If control leaves the loop, no comparison ever matched, so the target is absent from the cache. Return -1.

The solution

Rotation-aware binary search
def binary_search_impl(arr: list[int], target: int) -> int:
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        if arr[low] <= arr[mid]:
            if arr[low] <= target < arr[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:
            if arr[mid] < target <= arr[high]:
                low = mid + 1
            else:
                high = mid - 1
    return -1
Plain binary search / bisect
Both assume the array climbs everywhere. On [4, 5, 6, 7, 0, 1, 2] searching for 0, they steer as if 0 sits before 4, land near index 0, and a bounds check finds arr[0] is 4, not 0, so they answer -1. The 0 was at index 4 the whole time.
Rotation-aware search
Before pruning, it asks which side of mid is genuinely sorted and whether 0 falls inside that side's range. That question walks it across the pivot to index 4 correctly, without ever scanning.

Common follow-up questions