Leetcode 33: Search in Rotated Sorted Array
General Idea
Basically on top of binary search, we make use of the first item in the list, which gives information about whether the smallest is on the left or right side of the current chosen [mid], and handle each case by case. To clarify: If no rotate is made, the algorithm just works as usual.
Explanation at each step within the code below.
Code
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if target < nums[mid]:
if nums[mid] < nums[left]:
"""
Smallest on the left side inclusively,
so if target is less than, it is only
possible on the left.
"""
right = mid - 1
else:
"""
If the smallest is on the right side of mid
caused by a possible rotate.
"""
if target > nums[left]:
"""
nums[left] < target < nums[mid],
since smallest on the right side,
it's a perfect interval (non-decreasing).
"""
right = mid - 1
elif target == nums[left]:
return left
else:
"""
Target possibly on the second half of
the right part.
"""
left = mid + 1
elif target > nums[mid]:
if nums[mid] < nums[left]:
"""Smallest on the left inclusively."""
if target > nums[right]:
"""
Since smallest on the left, leaving
the right part non decreasing. So if
greater, must only possible on the
first part of the left.
"""
right = mid - 1
elif target == nums[right]:
return right
else:
"""
nums[mid] < target < nums[right],
since smallest on the left side,
it's a perfect interval (non-decreasing).
"""
left = mid + 1
else:
"""
Smallest on the right = left part non-decreasing,
therefore if target greater than mid, must be in
the first part of right if exists.
"""
left = mid + 1
else: # target == nums[mid]:
return mid
return -1
Enjoy Reading This Article?
Here are some more articles you might like to read next: