Search in Rotated Sorted Array

Problem

An ascending array of distinct integers has been rotated at an unknown pivot. Given the rotated array and a target, return the index of the target, or -1 if it is not present. The solution must run in O(log n) time.

Approach

Run a binary search. At any midpoint, at least one half of the range is still sorted.

Compare the low and middle values to find which half is sorted. If the target falls inside that sorted half's range, search there; otherwise search the other half.

Each step still halves the range, so the rotation costs nothing extra.

Solution

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

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

            if nums[low] <= nums[mid]:
                if nums[low] <= target < nums[mid]:
                    high = mid - 1
                else:
                    low = mid + 1
            else:
                if nums[mid] < target <= nums[high]:
                    low = mid + 1
                else:
                    high = mid - 1

        return -1

Complexity

• Time: O(log n).
• Space: O(1).

Edge cases

• An array that was not rotated works the same way.
• A single element either matches or returns -1.
• The values are distinct; duplicates are the harder Search in Rotated Sorted Array II.