Search in a rotated array

Lesson 4.4 · Medium · Half is sorted · 10 min · by Vinay C

We'll cover the following

Overview
Watch it run
The idea
Complexity
In Python
Summary

A sorted array was rotated at some pivot, like 4 5 6 7 0 1 2. Find the target in O(log n).

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

lo340

501

542

593

684

725

766

807

858

mid869

9110

9211

9312

9713

114

915

1116

1717

2718

hi2819

Left half (34..86) is in order. 59 falls inside it, so go left.

lo 0 · hi 19 · mid 9

1 / 5

The idea

Complexity

Time	Space	Why
`O(log n)`	`O(1)`	One half is always sorted, so one half is dropped each step.

In Python

def search(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 sorted
            if nums[lo] <= target < nums[mid]: hi = mid - 1
            else: lo = mid + 1
        else:                                # right half sorted
            if nums[mid] < target <= nums[hi]: lo = mid + 1
            else: hi = mid - 1
    return -1

</> Now code it →Try it on LeetCode: Search in Rotated Sorted Array →

Summary: say it in the interview

After rotation, at least one half around the middle is still sorted. Find that half, check whether the target lies inside its range, and keep that half or discard it.
Time O(log n), space O(1). One half is always sorted, so one half is dropped each step.