menu

[LeetCode] 033. Search in Rotated Sorted Array *

Problem (Medium)

033. Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of $O(\log n)$.

Example 1:

  • Input: nums = [4,5,6,7,0,1,2], target = 0
  • Output: 4

Example 2:

  • Input: nums = [4,5,6,7,0,1,2], target = 3
  • Output: -1

Idea

  • First, find the smallest numbers’s index;
  • Second, regular binary search to find target.

Solution

class Solution1:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        # Find the smallest number's index
        low, high = 0, len(nums)-1
        while low < high:
            mid = (low + high) // 2
            if nums[mid] > nums[high]:
                low = mid + 1
            else:
                high = mid
        # the resulting low==high is the rotation offset amount
        rotation = low
        low, high = 0, len(nums)-1
        while low <= high:
            mid = (low + high) // 2
            realmid = (mid + rotation) % len(nums)
            if nums[realmid] == target:
                return realmid
            if nums[realmid] > target:
                high = mid - 1 
            else:
                low = mid + 1
        return -1

Complexity

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

Approach 2: Binary Search in One Loop

Idea

Solution

class Solution2:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        low, high = 0, len(nums)-1
        while low <= high:
            mid = (low + high) // 2
            if target == nums[mid]:
                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)$



KF

Comments