1. FlyPython首页
  2. 数据结构与算法
  3. leetcode题解

「LeetCode每日一题」—— 33. 搜索旋转排序数组

33. 搜索旋转排序数组

链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
难度:中等

题目

点击原文链接跳转查看题目

思路

这个题要求时间复杂度是O(log n),那指向的是二分查找。

如果我们先不考虑时间复杂度的要求,那我们可以通过库函数来做这个题,直接使用index来确定位置,代码见暴力方案。

现在我们考虑二分查找。

我们可以先计算mid,然后判断mid是在有序还是无序的部分。

如果mid<start,那mid在右边有序的部分
如果mid>=start,那mid在左边有序部分

如: [4,5,6,7,0,1,2] mid = 7
因为4 < 7,那 mid 左边一定有序。

mid = 7 > target,target < start,那target 不会在左边有序的部分,这一部分就可以丢掉,继续在右边查找。

代码见二分查找方案。

方案代码

暴力方案:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        try:
            return nums.index(target)
        except ValueError:
            return -1

二分查找:


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        """用二分法,先判断左右两边哪一边是有序的,再判断是否在有序的列表之内"""
        if len(nums) <= 0:
            return -1

        left = 0
        right = len(nums) - 1
        while left < right:
            mid = (right - left) // 2 + left
            if nums[mid] == target:
                return mid
            # 如果中间的值大于最左边的值,说明左边有序
            if nums[mid] > nums[left]:
                if nums[left] <= target <= nums[mid]:
                    right = mid
                else:
                    # 这里 +1,因为上面是 <= 符号
                    left = mid + 1
            # 否则右边有序
            else:
                # 注意:这里必须是 mid+1,因为根据我们的比较方式,mid属于左边的序列
                if nums[mid+1] <= target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid
                    
        return left if nums[left] == target else -1

原创文章,作者:flypython,如若转载,请注明出处:http://flypython.com/algorithm/leetcode/356.html