Leetcode 33: Search in Rotated Sorted Array
Published:
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]:
"""
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 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 and only if there are only one or two items in the range.
In which case check the next or terminate the while loop."""
left += 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
elif nums[mid] > nums[left]:
"""
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:
"""
If and only if there are only one
or two items in the range. In which case
check the next or terminate the while loop.
"""
left += 1
else: # target == nums[mid]:
return mid
return -1