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).

General idea

Structure of the rotated array

Front bigger than tail

We know the array is rotated that the latter portion is rotated to the front and nums[0] > nums[-1].

Partially sorted

Let’s assume the array is rotated at k. After the rotation, nums[k : end] is moved to the front and nums[0 : k] is sorted, so is nums[k + 1 : end].

Binary search

Since after the rotation, two parts of the array are still sorted. Furthermore, there is always more than or equal to half of the array sorted. So we can take the mid point, decide which half is sorted and apply binary sort accordingly

Take the midpoint

If nums[mid] < nums[low]

EG[5,6,0,1,2,3,4] That means the nums[low : mid] is not sorted and nums[low : mid] contains the whole rotation with the head of the original. This also means that nums[mid : high] is sorted and we can apply binary search to it.

1. If nums[mid] < target < nums[high] Recursively call binary search with nums[mid + 1:high]
2. Else It is possible that target is in nums[low:mid], recursively call binsearch with nums[low : mid]

If nums[mid] > nums[low]

That means nums[low : mid] is sorted and also nums[mid + 1 : end] might not be sorted. So we apply binary search on nums[low : mid] And we do the same as above.

Recursive solution code

    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        return self.search_rotated_array(nums, 0, len(nums) - 1, target)
    def search_rotated_array(self,nums, start, end, target):
        if start > end:
            return -1

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

        if nums[mid] < nums[end]:    #mid - end is sorted
            if nums[mid] < target <= nums[end]:  #target is within nums[mid + 1:end]
                return self.search_rotated_array(nums, mid + 1, end, target)
            else:   #target might be within nums[start, mid - 1]
                return self.search_rotated_array(nums, start, mid - 1, target)

        else:
            if nums[start] <= target < nums[mid]:
                return self.search_rotated_array(nums, start, mid - 1, target)
            else:
                return self.search_rotated_array(nums, mid + 1, end, target)

Details

Use of start and end to avoid parsing lists

Use of start > end to terminate the binary search.

Iterative solution