33.Search in Rotated Sorted Array

Tags: [sort], [binary_search], [trick]

Com: {fb}

Link: https://leetcode.com/problems/search-in-rotated-sorted-array/\#/description

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

(i.e.,0 1 2 4 5 6 7might become4 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.

Solution: Binary Search, Trick

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums or target is None:
            return -1

        return self.search_helper(nums, 0, len(nums) - 1, target)

    def search_helper(self, nums, start, end, target):
        # base case
        if start > end:
            return -1

        mid = start + (end - start) / 2
        if nums[mid] == target:
            return mid

        if nums[start] <= nums[mid]:
            # the sub array [start:mid + 1] is sorted.
            if nums[start] <= target < nums[mid]:
                # apply the binary search
                # we don't need to search end to mid, because nums[mid] != target.
                return self.binary_search(nums, start, mid - 1, target)
            else:
                return self.search_helper(nums, mid + 1, end, target)
        else:
            # the pivot must be between the start and mid,
            # so the sub array [mid:end + 1] is sorted.
            if nums[mid] < target <= nums[end]:
                # apply the binary search, 
                # we don't need search start from mid, because nums[mid] != target.
                return self.binary_search(nums, mid + 1, end, target)
            else:
                return self.search_helper(nums, start, mid - 1, target)

    def binary_search(self, nums, start, end, target):
        while start <= end:
            mid = start + (end - start) / 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                start = mid + 1
            else:
                end = mid - 1

        return -1

Revelation:

• If nums[start] <= nums[mid], means the sub array [start:mid + 1] is sorted, else means the pivot must be between the start and mid - 1, so that means the sub array [mid:end + 1] is sorted. (We can do this judgement, because there is no duplicates)
• Before we do binary search, we must need to checkout the followings:

if nums[start] <= target < nums[mid]:

if nums[mid] < target <= nums[end]:

• to make sure the target will be in the range. If we don't check the nums[start] and nums[end], the case nums = [3, 1], target = 1, we get the wrong result.

Note:

• Time complexity = O(lgn), n is the number of the elements of the given nums.