题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。 编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,否则返回 false。
思路
详见链接
代码
class Solution:def search(self, nums:List[int], target:int)->bool:n = len(nums)if n == 0:return Falseleft = 0right = n - 1while left <= right:mid = left + (right - left)//2 #此写法防止溢出,mid = (left +right) / 2 这种写法可能会溢出。 (注: mid = left + (right - left) / 2 和 mid = (left +right) / 2 这两种写法是一个意思,不过前一种写法更保险一点)if nums[mid] == target:return Trueif nums[left] == nums[target] == nums[right]:left += 1right += 1elif nums[left] <= nums[mid]:if nums[left] <= target <nums[right]:right = mid - 1else:left = mid + 1else:if nums[mid] < target <= nums[right]:left = mid + 1else:right = mid - 1return False
如果觉得《LeetCode81. 搜索旋转排序数组 II(二分查找)》对你有帮助,请点赞、收藏,并留下你的观点哦!