33. 搜索旋转排序数组 [medium]

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

通过次数137,485 | 提交次数360,168

Second Try

2020-07-02

写个非递归版本的，速度快了一点点。

# 搞个非递归版本
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not len(nums):
            return -1
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid 
            # if left part is ordered
            if nums[left] <= nums[mid]: # mid may be equal to left
                # if in the left ordered part
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                # in the right ordered part
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1

执行用时：24 ms, 在所有 Python 提交中击败了57.81%的用户
内存消耗：12.9 MB, 在所有 Python 提交中击败了25.00%的用户

First Try

2020-07-02

依然是第一眼不知道该怎么用二分法来做，毕竟复杂度O(lgN)要求在这里摆着，遍历一遍都变成来O(N).

看了题解才知道诀窍，由于本来已经是有序数组，旋转了一小部分，那么于这一整个数组，切一半后总归有一半是有序的。接下来就是判断是否在有序的这一半里，如果不在说明在另一半（如果直接从无序那一半判断则没法操作）。就这样一步步对半，终于实现了O(lgN)的算法，也是一个标准的二分法。

判断某一半是否有序，只需要使用第一个元素跟最后一个元素比较就可以。知道这个诀窍后，就简单多了。

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        # 没想到就算是无序版本，分成两半的话总归有一半是有序版本
        # 然后依然可以继续不停分下去，每次找出有序的一半，判断是在哪一边
        if not len(nums):
            return -1
        def divsearch(nums, target, left, right):
            # print(nums, target, left, right)
            if left > right:
                return -1
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            # 普通的二分法，是通过nums[mid]与target进行比较
            # 此处是为了判断是否有序，然后再看是否能扔到对面去
            if nums[left] <= nums[mid]:  # 如果是<则错误，因为left与mid可能相等
                # 有序的一半
                if nums[left] <= target < nums[mid]:
                    return divsearch(nums, target, left, mid - 1)
                else:
                    return divsearch(nums, target, mid + 1, right)
            else:
                # 有序的一般在(mid, right]这边
                if nums[mid] < target <= nums[right]:
                    return divsearch(nums, target, mid + 1, right)
                else:
                    return divsearch(nums, target, left, mid - 1) 
        return divsearch(nums, target, 0, len(nums)-1)

执行用时：32 ms, 在所有 Python 提交中击败了12.59%的用户
内存消耗：13 MB, 在所有 Python 提交中击败了25.00%的用户

作弊版本

不按照二分法写的版本，复杂度本来是超标的，结果速度竟然更快了。

# 搞个作弊版本看看,速度竟然是92%,可怕。。
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if target not in nums:
            return -1
        return nums.index(target)

执行用时：16 ms, 在所有 Python 提交中击败了92.11%的用户
内存消耗：12.9 MB, 在所有 Python 提交中击败了25.00%

33. 搜索旋转排序数组 [medium]​

Second Try​

First Try​

33. 搜索旋转排序数组 [medium]

Second Try

First Try