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

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

flypython • • leetcode题解

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

赞 (0)
flypythonflypython
0 0 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
« 上一篇 26/04/2020 11:06
下一篇 » 28/04/2020 11:07

相关推荐