Search in Rotated Sorted Array

The problem description can be found in LeetCode.

Approach

Whenever we have a sorted sequence, there is a pretty high chance that Binary Search must be used.

Of course, there are variations of Binary Search. Here, the array is sorted, but rotated, which means that there are two distinct sorted lists.

Let's take at an example:

lst = [6, 7, 1, 2, 3, 4, 5]
       <-->
             <------------>
       L        M        R

We can obtain two arrays by splitting the input one: [L, M) and (M, R], where L, M and R are left, mid and right, respectively.

We can also notice that (M, R] is the sorted array. In fact, for each middle element, either the left array or the right one are actually sorted.

Since only one of them is actually sorted, we can use this information to change either the left or the right pointer, depending on the values of the mid element and the target one.

Solution

from typing import List


class Solution:
    def search(self, 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

            num_left = nums[left]
            num_mid = nums[mid]
            num_right = nums[right]

            is_left_ordered = num_left <= num_mid
            is_right_ordered = num_mid <= num_left
            assert is_left_ordered or is_right_ordered

            if is_left_ordered:
                if num_left <= target <= num_mid:
                    right = mid - 1
                else:
                    left = mid + 1
            elif is_right_ordered:
                if num_mid <= target <= num_right:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

Complexity

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

Where $n$ is the size of the nums list.