33. Search in Rotated Sorted Array
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
题意
这道题的意思是给你一个旋转数组（也就是一个升序的数组从中间截断，再把前面的一部分拼接到后面），在这个旋转数据内以\(O(logn)\)的时间复杂度来查找一个数
见到\(O(logn)\)这个时间复杂度来查找，那八九不离十是要用二分查找了
这个题目二分查找的特殊之处在于我们需要判断一下截断点是在前半部分还是后半部分, 分情况处理
- 如果
截断点在前半部分， target在前半部分，需要在前半部分进一步判断 - 如果
截断点在前半部分，target在后半部分，问题退化为普通的二分查找 - 如果
截断点在后半部分， target在前半部分，问题退化为普通的二分查找 - 如果
截断点在后半部分，target在后半部分，需要在后半部分进一步判断
解法
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left = 0
right = len(nums) - 1
while left <= right:
mid = (right + left) // 2
if target == nums[mid]:
return mid
if nums[mid] >= nums[left]:
if target >= nums[left] and target <= nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if target >= nums[mid] and target <= nums[right]:
left = mid + 1
else:
right = mid -1
return -1
81. Search in Rotated Sorted Array II
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
You are given a target value to search. If found in the array return true, otherwise return false.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Follow up:
- This is a follow up problem to Search in Rotated Sorted Array, where
numsmay contain duplicates. - Would this affect the run-time complexity? How and why?
题意
这道题是上一题的follow up，区别在于nums可能有重复的数，并且最后返回true或false，表示能否找到
方法是在上一题的基础上加入判断nums[left] == nums[mid],nums[right] == nums[mid]的分支，代表无法判断该区间是否旋转，需要遍历查找
解法
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left = 0
right = len(nums) - 1
while left <= right:
mid = (right + left) // 2
if target == nums[mid]:
return True
if nums[mid] > nums[left]:
if target >= nums[left] and target <= nums[mid]:
right = mid - 1
else:
left = mid + 1
elif nums[mid] < nums[right]:
if target >= nums[mid] and target <= nums[right]:
left = mid + 1
else:
right = mid -1
elif nums[left] == nums[mid]:
left += 1;
elif nums[right] == nums[mid]:
right -= 1;
return False
