Search in Rotated Sorted Array - LeetCode
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). Example 1: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4
- code
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
mid = l + (r - l) // 2
if target == nums[mid]: return mid
elif nums[l] <= nums[mid]: # left part sorted [1,3]
if nums[l] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
else: # right part sorted
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid - 1
return -1