How to Search a Rotated Sorted List in Python

Binary search a pivot-rotated sorted list for a target value and return its index in O(log n) time.

Medium Python 3.9+ Aug 9, 2026 Algorithms & data structures 12 views 0 copies

binary-search rotated-array search-algorithm

Python code

31 lines

Python 3.9+

from typing import List

def search_rotated(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid

        # left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

if __name__ == "__main__":
    nums = [4, 5, 6, 7, 0, 1, 2]
    print(search_rotated(nums, 0))  # expected: 4
    print(search_rotated(nums, 3))  # expected: -1
    print(search_rotated([1], 1))    # expected: 0
    print(search_rotated([1, 3], 3)) # expected: 1

Output

stdout

How it works

The algorithm leverages standard binary search but adapts it to handle a rotation. At each step, it determines which half of the current subarray is sorted by comparing the leftmost element with the middle. If the target lies within the sorted half's bounds, it narrows the search there; otherwise, it searches the other half. This works because a rotated sorted array still has one half that is normally sorted, allowing us to safely discard half the search space each iteration. The loop runs in O(log n) time and uses only O(1) extra space.

Common mistakes

Forgetting to check the sorted half bounds using <= and < in the correct order (off-by-one errors).
Assuming the array is always rotated or handling edge cases like arrays of length 1 or 2 incorrectly.
Not handling duplicates, which can break the sorted-half detection and require a modified approach.
Returning the target value itself instead of its index.

Variations

Implement iteratively with a while loop for clarity (as done here).
Use a recursive binary search that passes left/right indices as arguments.

Real-world use cases

Finding an element in a rotated dataset like a rolling log index or a circular buffer snapshot.
Searching in a sorted array that has been shifted, such as a list of versioned configuration keys after a rotation.
Implementing efficient lookup in a sorted list that is rotated by a known pivot in a database index or cache.

How to Search a Rotated Sorted List in Python

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Keep learning

Tutorials

Quizzes