LeetCode33:搜索旋转排序数组

题目

题目地址：

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

题目描述：

假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。 你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。(其实就是提醒你使用二分算法)

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0

输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3

输出: -1

相关题目

思路

根据题目要求时间复杂度为 O(log n) 级别，就是告诉你可能会使用二分算法
这道题是二分算法题的一道变体
因为二分算法要求数组是有序的，但是在本题中，数组会在某个点上进行旋转，需要做一些处理

基本思路是将数组从中间分成两部分，其中肯定有一部分是有序的（要么是前半部分，要么是后半部分）
这里需要分两种情况

• 一种是从中间分开后，前半部分是有序的，后半部分是无序的，如下图中的左边

检查 target 值是不是在前半部分，是的话检查的范围缩小到这一部分，即 r = mid -1
不是的话，就说明 target 值在后半部分，即 l = mid + 1

• 一种是从中间分开后，后半部分是有序的，前半部分是无序的，如下图中的右边

检查 target 值是不是在后半部分，是的话检查的范围缩小到这一部分，即 l = mid + 1
不是的话，就说明 target 值在前半部分，即 r = mid - 1

l：表示 left 的意思，下面程序用 low 替换
r：表示 right 的意思，下面程序用 high 替换

代码

测试用例

• 数组为空
• target 在数组中
  • 在数组中间、左右两侧的情况
• target 不在数组中

程序

时间复杂度：O(logn)
空间复杂度：O(1)

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