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
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
题意
一个排序数组经过位置方式旋转后形成一个新的数组，在新的数组中查找目标值，返回目标值位置，如果没有返回-1.
思路
- 用一个新的数组深度拷贝原数组，新数组排序后采用二分查找，找到值再去原数组中找位置。
def search(self, nums: List[int], target: int) -> int:
new_nums = nums.copy()
new_nums.sort()
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if new_nums[mid] < target:
left = mid + 1
elif new_nums[mid] > target:
right = mid - 1
else:
for n, i in list(zip(nums, range(len(nums)))):
if new_nums[mid] == n:
return i
return -1
- 先找到旋转位置，rotateIndex，即数组最小值，找到之后，再分区二分查找。
def search2(self, nums: List[int], target: int) -> int:
def findRotateIndex(nums, left, right):
if nums[left] < nums[right]:
return 0
while left <= right:
rotateIndex = (left + right) // 2
if nums[rotateIndex] > nums[rotateIndex + 1]:
return rotateIndex + 1
else:
if nums[left] > nums[rotateIndex]:
right = rotateIndex - 1
else:
left = rotateIndex + 1
def searchHelper(sub_nums, target):
if len(sub_nums) == 1:
return 0 if sub_nums[0] == target else -1
left = 0
right = len(sub_nums) - 1
while left <= right:
mid = (left + right) // 2
if sub_nums[mid] < target:
left = mid + 1
elif sub_nums[mid] > target:
right = mid - 1
else:
return mid
return -1
if not nums:
return -1
if len(nums) == 1:
return 0 if nums[0] == target else -1
rotateIndex = findRotateIndex(nums, 0, len(nums) - 1)
if nums[rotateIndex] == target:
return rotateIndex
elif nums[0] > target:
res = searchHelper(nums[rotateIndex:], target)
return rotateIndex + res if res != -1 else -1
elif nums[-1] < target:
return searchHelper(nums[:rotateIndex], target)
else:
return searchHelper(nums, target)
