1. 什么是旋转排序数组

力扣的题目里对旋转数组的说明如下：

整数数组 nums 按升序排列，数组中的值 互不相同 。 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

简单的来说，就是一个数组由左右两个升序数组构成，而且左数组的最小值大于右数组的最大值（在变式中这个关系是大于等于）

2. 常用方法：二分查找

以升序数列为例，比较一个元素与数列中的中间位置的元素的大小，如果比中间位置的元素大，则继续在后半部分的数列中进行二分查找；如果比中间位置的元素小，则在数列的前半部分进行比较；如果相等，则找到了元素的位置。每次比较的数列长度都会是之前数列的一半，直到找到相等元素的位置或者最终没有找到要找的元素。

  1. def BinarySearch(nums,target):
  2.     left = 0
  3.     right = len(nums) - 1
  4.     while left <= right:
  5.         middle = (left + right) // 2
  6.         if nums[middle] == target:
  7.             return middle
  8.         elif nums[middle] > target:
  9.             right = middle - 1
  10.         else:
  11.             left = middle + 1

其实这里应该写点思考总结啥的，但是我今天心情不好脑子也不好，所以还是算了（躺平.jpg

3. 示例

下面列出leetcode中的四个旋转排序数组的题目：
33. 搜索旋转排序数组
81. 搜索旋转排序数组Ⅱ
153. 寻找旋转排序数组的最小值
154. 寻找旋转排序数组中的最小值 Ⅱ

33和81搜索的是指定值，153和154搜索的是最小值，81和154允许有重复元素出现

33

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

81

  1. class Solution:
  2.     def search(self, nums: List[int], target: int) -> bool:
  3.         if not nums:
  4.             return False
  5.         left = 0
  6.         right = len(nums) - 1
  7.         if right == 0:
  8.             return nums[0] == target
  10.         while left <= right:
  11.             middle = (left + right) // 2
  12.             if nums[middle] == target:
  13.                 return True
  14.             if nums[left] == nums[middle] and nums[middle] == nums[right]:
  15.                 left += 1
  16.                 right -= 1
  17.             # 两个旋转数组的区别就在上面这个if，你并不总能判断出来哪一半是有序的
  18.             elif nums[left] <= nums[middle]:
  19.                 if nums[left] <= target < nums[middle]:
  20.                     right = middle - 1
  21.                 else:
  22.                     left = middle + 1
  23.             else:
  24.                 if nums[middle] < target <= nums[right]:
  25.                     left = middle + 1
  26.                 else:
  27.                     right = middle - 1
  28.         return False

153

  1. class Solution:
  2.     def findMin(self, nums: List[int]) -> int:
  3.         left = 0
  4.         right = len(nums) - 1
  5.         while left <= right:
  6.             middle = (left + right) // 2
  7.             if nums[middle] < nums[right]:
  8.                 right = middle - 1
  9.             else:
  10.                 left = middle + 1
  11.         return nums[left]

154

  1. class Solution:
  2.     def findMin(self, nums: List[int]) -> int:
  3.         left = 0
  4.         right = len(nums) - 1
  5.         while left < right:
  6.             middle = (left + right) // 2
  7.             if nums[middle] < nums[right]:
  8.                 right = middle
  9.             elif nums[middle] > nums[right]:
  10.                 left = middle + 1
  11.             else:
  12.                 right -= 1
  13.         return nums[left]