Description
Find target's index in a rotated ascending array with distinct values, or return -1.
Solution
def search(nums, target):
left, right = 0, len(nums)-1
while left <= right:
mid = (left+right)//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
elif nums[mid] < target <= nums[right]:
left = mid+1
else:
right = mid-1
return -1Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[4,5,1,2,3],2]- Output
3
Target 2 is at index 3.
Example 2
- Input
[[1],0]- Output
-1
Target 0 is absent.
Example 3
- Input
[[3,1],3]- Output
0
The target is the first entry.
Approach
Identify the sorted half at each step and test whether the target lies inside it.
Time & space
O(log n) time; O(1) space. Here n is the input length.