LC 33搜索旋转排序数组Search in Rotated Sorted Array　中等

在经过一次旋转的升序数组中查找 target，返回下标否则返回 -1，要求 O(log n)。

思路 二分判哪半有序（nums[left]<=nums[mid] 即左半有序），再判 target 是否落在有序半段内缩小区间。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1