Leetcode 33 Search in Rotated Sorted Array

题目介绍

假定一个升序序列，在某个下标处发生了旋转，例如[0,1,2,4,5,6,7]=>[4,5,6,7,0,1,2]。给定一个target，要求在O(logn)的时间复杂度内进行查找，如果存在返回下标，否则返回-1。假定数组中不存在重复的数字。

Examples：

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Solution

时间复杂度在O(logn)，说明只能使用二分查找。对于这个数组，可能有下面几种情况：

1. nums[end]<nums[mid]：表明右半部分的值是旋转而来的，左半部分是单调的
   1. [4,5,6,7,8,0,1,2]
   2. [4,5,6,7,0,1,2]
2. nums[end]>nums[mid]: 表明右半部分是单调的
   1. [0,1,2,3,4,5,6,7,8]
   2. [8,0,1,2,3,4,5,6,7]

因此，每次查找target的时候，首先确定是否在单调的部分。

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        start, end = 0, len(nums)-1
        while start <= end:
            mid = start + (end-start)/2
            if nums[mid] == target:
                return mid
            if nums[end] < nums[mid]:
              	# 可以确定落在左边单调递增区间
                if nums[mid] > target and nums[start] <= target:
                    end = mid -1
                else:
                    start = mid + 1
            else:
              	# 可以确定落在右边单调递增区间
                if nums[mid] < target and nums[end] >= target:
                    start = mid + 1
                else:
                    end = mid -1
        return -1

延伸

在旋转数组中查找指定数的还有Leetcode 81 Search in Rotated Sorted Array II，它的不同之处在于数组中可能出现重复的数。当nums[end]==nums[mid]时，并不能判断在左边还是右边是单调区间，由于这个数并不等于target，因此可以将它排除在外(end -= 1)。

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        start, end = 0, len(nums)-1
        
        while start <= end:
            mid = start + (end - start) / 2
            if nums[mid] == target:
                return True
            else:
                if nums[end] < nums[mid]:
                    if nums[mid] > target and nums[start] <= target:
                        end = mid - 1
                    else:
                        start = mid + 1
                elif nums[end] > nums[mid]:
                    if nums[mid] < target and nums[end] >= target:
                        start = mid + 1
                    else:
                        end = mid - 1
                else:
                    end -= 1
        return False

Leetcode 33 Search in Rotated Sorted Array

原文：https://www.cnblogs.com/yuyinzi/p/13873473.html