# The Silent Locator > Every lookup should cost you less than the one before it. Canonical URL: 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`. ## 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. > **Trick to solving** > > At every step exactly one side of `mid` is still in sorted order, because the single wrap can only fall on one side. Work out which side that is by comparing `arr[low]` to `arr[mid]`, then check whether the target lies inside that ordered side's value range. If it does, search there; if it does not, the target must live in the messy half, so search the other side. --- ### 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** ```python 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 ``` > **Time and space** > > Time: O(log n). Each iteration still discards half the window, exactly like plain binary search, because only one extra comparison decides which half. Space: O(1), three integer variables and no recursion. **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. > **Interviewers watch for** > > The tell of a shaky candidate is picking a half from `arr[mid]` versus `target` alone. On a rotated window that reasoning discards the correct half half the time. A strong candidate first proves which side is ordered, then prunes only the side that cannot contain the target. > **Common pitfall** > > The equality in `arr[low] <= arr[mid]` is load-bearing. With a one or two element window `low` and `mid` can coincide, and dropping the `=` misclassifies the sorted side, sending the search down the wrong branch right at the pivot. --- ## Common follow-up questions - What breaks if the IDs are no longer distinct, and how would you recover? _(Duplicates break the arr[low] <= arr[mid] test, since arr[low], arr[mid], and arr[high] can all be equal while the pivot hides on either side.)_ - How would you locate the pivot, that is the index of the smallest ID, without knowing the target? _(Tests finding the rotation point itself with a single binary search.)_ - What changes when the rotated cache is too large to hold in memory? _(Tests external-search strategies and block or memory-mapped access.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/the_silent_locator) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.