打卡题目：leetcode第33题，搜索旋转排序数组
    相似题目：81、153
    image.png

    【思路】

    1. 暴力解法：for循环遍历，找到目标值。
    2. 二分查找特殊变形。必须理解到：不管怎么旋转，总有一部分区间是有序的。比如，1->mid和mid->r之中至少有一个是有序的。我们的逻辑就是：判断target是否在有序区间中，在则将另一个指针移动到有序区间内，否则将有序区间的指针（除mid外的另一个边界指针）移动到有序区间外。

    【代码】

    1. class Solution:
    2.     def search(self, nums: List[int], target: int) -> int:
    3.         if not nums:
    4.             return -1
    5.         l, r = 0, len(nums)-1
    6.         while l <= r:
    7.             mid = l + (r - l) // 2
    8.             if nums[mid] == target:
    9.                 return mid
    10.             if nums[l] <= nums[mid]:
    11.                 if nums[l] <= target < nums[mid]:
    12.                     r = mid - 1
    13.                 else:
    14.                     l = mid + 1
    15.             else:
    16.                 if nums[mid] < target <= nums[r]:
    17.                     l = mid + 1
    18.                 else:
    19.                     r = mid - 1
    20.         return -1