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.
- If nums[mid] < target < nums[high] Recursively call binary search with nums[mid + 1:high]
- 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)