Search in Rotated Array

Search in Rotated Array

Step 1 of 7

target3rotationat index 3

m

12

15

18

2

3

6

9

lo

hi

Sorted, then rotated: values climb, drop once at index 3, then climb again.

The Idea

A sorted array that has been rotated still has one fully sorted half at every split. Work out which side is in order, then check whether the target falls inside it. Binary search survives intact, still O(log n).

Real-World Example

Think of a daily log file that wraps at midnight. Timestamps climb, restart once, then climb again, so wherever you open it there is always one cleanly ordered side to reason about.

The Code

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:              # left half is sorted
            if nums[lo] <= target < nums[mid]: hi = mid - 1
            else:                              lo = mid + 1
        else:                                  # right half is sorted
            if nums[mid] < target <= nums[hi]: lo = mid + 1
            else:                              hi = mid - 1
    return -1
# search_rotated([6, 7, 9, 1, 2, 4], 2) -> 4

Your turn

Put the steps in the right order.

1. 1Discard the half that cannot contain the target↑↓
2. 2Compute mid and compare it to the target↑↓
3. 3Decide which half is sorted↑↓
4. 4Check whether the target lies inside that sorted half↑↓

Check order

Mini quiz

1 / 3

In a rotated sorted array, at any split point:

• ABoth halves are sorted
• BAt least one half is sorted
• CNeither half is sorted
• DThe array must be re-sorted first