Search in Rotated Sorted Array

Description:

Suppose a sorted array 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.

Solution 1: (Python)

The idea is to find the pivot first. Suppose the pivot is mid, then the boundaries are nums[0], nums[mid], nums[mid+1], nums[final]. Compare the target with the value with the boundaries, and then do binary search.

• Time: O(n + logn) = O(n)

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        mid = 0
        while mid < len(nums) - 1 and nums[mid] < nums[mid + 1]:
            mid += 1
        if mid == len(nums) - 1:
            if target > nums[-1] or target < nums[0]:
                return -1
            else:
                return self.binarySearch(nums, 0, len(nums) - 1, target)
        if target < nums[mid+1] or target > nums[mid] or (target < nums[0] and target > nums[-1]):
            return -1
        elif target >= nums[mid+1]:
            if target <= nums[-1]:
                return self.binarySearch(nums, mid+1, len(nums), target)
            elif target >= nums[0] and target <= nums[mid]:
                return self.binarySearch(nums, 0, mid, target)


    def binarySearch(self, nums, low, high, target):
        if low <= high:
            mid = int((low + high) / 2)
            if nums[mid] == target:
                return mid
            elif target < nums[mid]:
                return self.binarySearch(nums, low, mid - 1, target)
            else:
                return self.binarySearch(nums, mid + 1, high, target)
        else:
            return -1

Solution 2:

In solution 1, O(n) comes from searching for the pivot. It is feasible to find the pivot in O(lgn) time with binary search again.

• Time: O(lgn)

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if(len(nums) == 0): return -1 
        elif (len(nums) == 1):
            if(nums[0]!=target): return -1
            else: return 0
        elif (len(nums) == 2):
            if(nums[0] == target): return 0
            elif(nums[1] == target): return 1
            else: return -1

        high = len(nums) - 1
        low = 0
        while(low < high):
            if(nums[high] > nums[low]): break
            mid = int((high + low) / 2)
            if(nums[mid] > nums[high]):
                low = mid + 1
            else:
                high = mid
        min = low
        if(min == 0):
            if target > nums[-1] or target < nums[0]:
                return -1
            else:
                return self.binarySearch(nums, 0, len(nums) - 1, target)
        else:
            mid = min - 1

        if target < nums[mid + 1] or target > nums[mid] or (target < nums[0] and target > nums[-1]):
            return -1
        elif target >= nums[mid + 1]:
            if target <= nums[-1]:
                return self.binarySearch(nums, mid + 1, len(nums)-1, target)
            elif target >= nums[0] and target <= nums[mid]:
                return self.binarySearch(nums, 0, mid, target)

    def binarySearch(self, nums, low, high, target):
        if low <= high:
            mid = int((low + high) / 2)
            if nums[mid] == target:
                return mid
            elif target < nums[mid]:
                return self.binarySearch(nums, low, mid - 1, target)
            else:
                return self.binarySearch(nums, mid + 1, high, target)
        else:
            return -1