问题链接
https://leetcode.cn/problems/search-in-rotated-sorted-array/description/
解题思路
这个题目要求复杂度了。我们不要慌,首先分析一下数据。
也就是说,这个数组是由2个上升子序列组成的。所以,我们如果用传统的二分法,是不太合适的,因为它并不是一个整体有序的数据。
但是,我们发现,如果用传统二分的话,我们把这个数组劈成2份。它有3个结果:
劈开后,左侧有序,右侧有序
劈开后,左侧有序,右侧无序
劈开后,左侧无序,右侧有序
我们只需要在有序的那一侧搜索即可。
代码
class Solution: def search(self, nums, target: int) -> int: left_val, right_val = nums[0], nums[-1] left, right = 0, len(nums)-1 while left <= right: mid = (left+right)>>1 if nums[mid] == target: return mid elif nums[0] <= nums[mid]: # 证明左侧有序 if left_val <= target < nums[mid]: right = mid - 1 else: left = mid + 1 else: # 右侧有序 if nums[mid] < target <= right_val: left = mid + 1 else: right = mid - 1 return -1
标签:数组,nums,33,有序,劈开,排序,右侧,left From: https://www.cnblogs.com/bjfu-vth/p/17044777.html