LeetCode 33: Search in Rotated Sorted Array

Problem Restatement

We are given an integer array nums.

The array was originally sorted in ascending order, with all distinct values. Before being passed to us, it may have been rotated at some unknown pivot.

For example:

[0, 1, 2, 4, 5, 6, 7]

can become:

[4, 5, 6, 7, 0, 1, 2]

We are also given an integer target.

Return the index of target if it exists in nums. Otherwise, return -1.

The required runtime is O(log n), so a linear scan is too slow for the intended solution. The array length is at least 1, all values are unique, and nums is an ascending array that is possibly rotated.

Input and Output

Function shape:

def search(nums: list[int], target: int) -> int:
    ...

Examples

Example 1:

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

The value 0 appears at index 4.

Return:

4

Example 2:

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

The value 3 does not appear in the array.

Return:

-1

Example 3:

nums = [1]
target = 0

There is only one value, and it is not the target.

Return:

-1

First Thought: Linear Search

The simplest solution is to scan every index.

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        for i, num in enumerate(nums):
            if num == target:
                return i

        return -1

This works because it checks every element.

Problem With Linear Search

Linear search takes O(n) time.

The problem asks for O(log n) time, so we need a binary-search-style solution.

The array is rotated, so the whole array may not be sorted. But it still has useful order.

At every midpoint, at least one half is sorted.

For example:

nums = [4, 5, 6, 7, 0, 1, 2]

If mid points to 7, then:

left half  = [4, 5, 6, 7]
right half = [0, 1, 2]

Both sides are sorted here.

In other cases, one side contains the rotation break, but the other side is sorted.

That is enough to decide which half can contain the target.

Key Insight

Use binary search, but first determine which half is sorted.

For a window:

left ... mid ... right

There are two cases.

If:

nums[left] <= nums[mid]

then the left half is sorted.

So if:

nums[left] <= target < nums[mid]

the target must be inside the left half.

Otherwise, search the right half.

If the left half is not sorted, then the right half must be sorted.

So if:

nums[mid] < target <= nums[right]

the target must be inside the right half.

Otherwise, search the left half.

The uniqueness of values keeps these comparisons clean.

Algorithm

Initialize:

left = 0
right = len(nums) - 1

While left <= right:

1. Compute the middle index.
2. If nums[mid] == target, return mid.
3. Check whether the left half is sorted.
4. If the left half is sorted, decide whether the target lies inside it.
5. Otherwise, the right half is sorted, so decide whether the target lies inside it.
6. Move left or right accordingly.

If the loop ends, return -1.

Correctness

At each step, the algorithm maintains a search window from left to right. If the target exists and has not already been returned, it must be inside this window.

The midpoint splits the window into two halves. Because the array came from a sorted array with one rotation, at least one of these halves is sorted.

When the left half is sorted, the condition nums[left] <= target < nums[mid] exactly describes whether the target value can lie in that sorted half. If it can, discarding the right half is safe. If it cannot, discarding the left half is safe.

When the right half is sorted, the condition nums[mid] < target <= nums[right] exactly describes whether the target value can lie in that sorted half. If it can, discarding the left half is safe. If it cannot, discarding the right half is safe.

Each iteration keeps the half that can still contain the target and removes the other half. Therefore, the target is never discarded. If the target exists, the loop eventually reaches it and returns its index. If the loop finishes, no candidate positions remain, so returning -1 is correct.

Complexity

Implementation

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 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

Code Explanation

We start with the full array as the search window.

left = 0
right = len(nums) - 1

The loop continues while the window is non-empty.

while left <= right:

The middle index is computed safely:

mid = left + (right - left) // 2

If the middle value is the target, we return immediately.

if nums[mid] == target:
    return mid

Now we decide which side is sorted.

If the left side is sorted:

if nums[left] <= nums[mid]:

then the target belongs to that side only when it lies between nums[left] and nums[mid].

if nums[left] <= target < nums[mid]:
    right = mid - 1
else:
    left = mid + 1

Otherwise, the right side is sorted.

else:

Then the target belongs to that side only when it lies between nums[mid] and nums[right].

if nums[mid] < target <= nums[right]:
    left = mid + 1
else:
    right = mid - 1

If the loop ends, the target does not exist in the array.

return -1

Testing

def check(nums: list[int], target: int, expected: int) -> None:
    actual = Solution().search(nums, target)
    assert actual == expected, (nums, target, actual, expected)

def run_tests():
    check([4, 5, 6, 7, 0, 1, 2], 0, 4)
    check([4, 5, 6, 7, 0, 1, 2], 3, -1)
    check([1], 0, -1)
    check([1], 1, 0)
    check([1, 3], 3, 1)
    check([3, 1], 1, 1)
    check([5, 1, 3], 5, 0)
    check([5, 1, 3], 3, 2)
    check([1, 2, 3, 4, 5], 4, 3)
    check([6, 7, 8, 1, 2, 3, 4, 5], 2, 4)

    print("all tests passed")

run_tests()

Test meaning: