Backend Engineer
Senior
programming
Given a rotated sorted array, write a function to search for a target value. If found, return its index; otherwise, return -1.
Function Signature
def search(nums: List[int], target: int) -> int:
Constraints
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
Examples
1. Input:
search([4,5,6,7,0,1,2], 0) Output:
4 2. Input:
search([4,5,6,7,0,1,2], 3) Output:
-1
```
def search(nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
```
Trusted by 100+ professionals preparing for interviews
Trusted by 100+ professionals
50+ Company Question Banks
5+ Supported Languages
Practice More Questions Like This
Generate unlimited interview questions with structured answers, code runner, and AI-powered walkthroughs.
Get Started Free