33_搜索旋转排序数组

类型：数组

• 33. 搜索旋转排序数组 💛 ⭐

  https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

  ❓ nums 本来是一个无重复元素的升序排列数组，其在某处进行了旋转，比如 [0,1,2,4,5,6,7] 在下标 3 处旋转后变为 [4,5,6,7,0,1,2]。给你旋转后的 nums，以及一个整数 target，如果 nums 中存在目标值 target，返回它的下标，否则返回 -1.

  💡 二分查找

  二分查找适用于有序数组。但是这个数组不是整体有序，而是局部有序。我们同样可以使用二分查找。

  将旋转后的数组分成两部分的话，其中一定有一部分是有序的。我们可以在分割出来的两个部分 [l, mid] 和 [mid + 1, r] 中查看哪个是有序的，并且可以直接判断 target 在不在那个部分，据此选择向哪个部分继续进行查找。

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

  时间复杂度：O(logN)，空间复杂度：O(1)