Leetcode: 33. Search in Rotated Sorted Array

Problem Statement

Patterns

Solution

Given an array \(a\) which is either sorted or it can be divided into two sorted subarrays such that the first subarray has numbers greater than the other one (e.g. \(a=[3, 4, 5, 1, 2]\)), return the index of \(target\) in the array or \(-1\) if it is not in the array.

An important observation is that either the array is sorted or for any index \(m\) either \(a[0..m]\) is sorted or \(a[m..(n-1)]\) is sorted. Let's use Binary Search to solve the problem. Denote \(s\), \(e\) and \(m\) as the start, end and pivot of the binary search. Consider the following for each iteration:

  • If \(a[m]=target\), the solution is \(m\).
  • If \(a[s..m]\) is sorted, search the left half of the array if \(a[s] \leq target \leq a[m]\); otherwise search the right half.
  • If \(a[m...e]\) is sorted, search the right half if \(a[m] \leq target \leq a[e]\); otherwise search the left half.

Time complexity of the solution is \(O(\log n)\) as the search space reduces by half on every iteration. The space complexity is \(O(1)\) as no extra memory is used. 

from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        start, end = 0, len(nums) - 1
        while start <= end:
            mid = start + (end - start) // 2
            if nums[mid] == target:
                return mid
            elif nums[0] <= nums[mid]:
                if nums[0] <= target < nums[mid]:
                    end = mid - 1
                else:
                    start = mid + 1
            else:
                if nums[mid] < target <= nums[-1]:
                    start = mid + 1
                else:
                    end = mid - 1
        return -1


assert Solution().search([4, 5, 6, 7, 0, 1, 2], 0) == 4
assert Solution().search([4, 5, 6, 7, 0, 1, 2], 3) == -1
assert Solution().search([1], 0) == -1

Cited by 2