🔢33. Search in Rotated Sorted Array
Medium | Grind 75 | July 28th, 2022
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4SOLUTION
Given that the question asks us to solve the question in O(log n), we know we need to somehow make use of binary search. The basic idea of binary search is to take half of the previous list until we find the target or run out of things to divide into two. Traditional binary search assumes that the integers in the list are sorted.
However, in this case, we have a sorted list that is rotated at a random pivot index. Given that the list is still sorted but rotated at a certain index, we can use that to our advantage. When we divide the list into two halves, it is guaranteed that one half will contain ascending sorted integers while the other will not. A simple way to check this is by checking the first and the last element for each half. For one half, the first element will be smaller than the last element (we will call this ordered half). Whereas for the other half, the first element will be greater than the last element (we will call this unordered half). Just like any other binary search, we will divide our list into two halves from the midpoint.
Since we now have our ordered and unordered list, we will first check if our target is in the range of the ordered list. If it is, we will take the ordered list and repeat the process of breaking it into halves until we find our target or run out of the list. If the target is in the range of the ordered list, we won't find the target in the unordered list because remember the list is sorted but just pivoted and all the values are unique. If our target is not in the range of the ordered list, we will take the unordered list and repeat the process.
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0 # initialize left as 0
right = len(nums)-1 #initialize right as the length of the list - 1
return self.binary_search(left, right,nums, target)
def binary_search(self,left, right, nums, target):
# we keep recursively calling the function until our left is more than right
if left <= right:
mid = left + (right - left)//2
if nums[mid] == target:
return mid
# first half of the list contains ordered integers.
if nums[left] <= nums[mid]:
# use first half if the target is within the max and min value of the first half
if nums[left] <= target <= nums[mid]:
return self.binary_search(left, mid-1, nums, target)
# we know the target is not in the first half so use the second half
else:
return self.binary_search(mid+1, right, nums, target)
# second half of the list contains ordered integers
else:
if nums[mid] <= target <= nums[right]:
return self.binary_search(mid+1, right, nums, target)
else:
return self.binary_search(left, mid-1, nums, target)
return -1 # have not found the target
TIME AND SPACE COMPLEXITY
TIME: given that we continuosly divide the list into half and only look at one half, time complexity is O(log n)
SPACE: O(1)we only have left and right which is constant.
Last updated