Search in Rotated Sorted Array

佚名 6年前 (2019-04-17) 随笔 1038人围观抢沙发百度已收录

问题：给定一个有序的数组和一个目标值，将数组分为两部分并且交换顺序后，从数组中找到目标值的位置，如果目标值不在数组中，则输出-1

示例：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

　　输出：2

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

　　输出：-1

解决思路：类似于二分查找，但条件判断要更复杂一些

Python代码：

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (left+right) // 2
            if nums[mid] < target:
                if nums[right] < nums[mid] or nums[right] >= target:
                    left = mid+1
                else:
                    right = mid - 1
            elif nums[mid] > target:
                if nums[left] > nums[mid] or nums[left] <= target:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                return mid
        return -1