# The Rotated Array

> Someone shuffled it. Now locate what you came for.

Canonical URL: <https://datadriven.io/problems/the_rotated_array>

Domain: Python · Difficulty: medium · Seniority: L5

## Problem

Given a rotated sorted list of distinct integers and a target value, return the index of the target or -1 if absent. The algorithm must run in O(log n) time.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **modified binary search** on a non-standard sorted array. It probes whether candidates can determine which half of the array is sorted at each step and use that information to narrow the search.

> **Trick to Solving**
>
> At every midpoint, one half of the array is guaranteed to be sorted. Check if the target lies within the sorted half. If yes, search there. If no, search the other half. This preserves O(log n) complexity despite the rotation.

---

### 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.

#### Step 3: Decide which half to search

If the target is within the sorted half's range, search there. Otherwise, search the other half.

#### Step 4: Return the index or -1

When `nums[mid] == target`, return mid. If the search space is exhausted, return -1.

---

### The solution

**Binary search with sorted-half detection**

```python
def search_rotated(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
```

> **Time and Space Complexity**
>
> **Time:** O(log n). The search space halves each iteration.
> 
> **Space:** O(1). Only pointer variables.

> **Interviewers Watch For**
>
> Can you trace through an example? Walking through `[4,5,6,7,0,1,2]` searching for 0 on a whiteboard shows you understand the branch logic. This is more convincing than just writing the code.

> **Common Pitfall**
>
> Using `<` instead of `<=` when checking `nums[left] <= nums[mid]`. When `left == mid`, the left 'half' is a single element, which is trivially sorted. Using `<` would incorrectly classify this case.

---

## Common follow-up questions

- What if the array could contain duplicates? _(Tests that worst case degrades to O(n) when duplicates prevent determining the sorted half.)_
- How would you find the rotation pivot index? _(Tests a separate binary search for the minimum element.)_
- What if the array were not rotated at all? _(Tests that the algorithm handles the unrotated case naturally.)_
- How does this relate to searching in a distributed sorted index? _(Tests understanding that sharded indices can have similar rotation at shard boundaries.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_rotated_array)
- [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). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.