问题链接

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