Search in Rotated Sorted Array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. You are given a target value to search. If found in the array return its index, otherwise return -1. Tags: Array
Try It!
Discussion
Video
Solution
class Solution:
def search(self, nums: List[int], target: int) -> int:
lo = 0
hi = len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if target == nums[mid]:
return mid
if nums[lo] <= nums[mid]:
if nums[lo] <= target <= nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] <= target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1