欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

33. Search in Rotated Sorted Array

程序员文章站 2022-07-15 19:45:09
...

https://leetcode.com/problems/search-in-rotated-sorted-array/description/
题意:给一个升序数组从中间翻转后的数组,还有一个target,用logn的复杂度搜索这个target,返回其下标,否则-1
思路:
如下图
33. Search in Rotated Sorted Array

由于是翻转数组,且无重复,因此nums[0]必然大于nums[n-1](为什么?写出来就知道),所有的数分成两支,每支内依然升序。问题是不知道断点在哪

因此可以先取mid,看target与mid是否在同一支上,若在同一支,可以直接在该支上做二分查找。

若不在同一支,例如mid在左,tar在右,则mid往右收缩;反之则mid往左收缩

class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        n = len(nums)
        lo, hi = 0, n-1
        while lo <= hi:  #二分查找
            mid = (lo + hi) // 2 
            if target > nums[0]:  #target在左分支
                if nums[mid] >= nums[0]:  #mid也在左分支
                    tmp = nums[mid]
                else:
                    tmp = float('inf')
            elif target == nums[0]:  #恰好等于左端点
                return 0
            elif target == nums[n-1]:  #恰好等于右端点
                return n-1
            else:  #target在右分支
                if nums[mid] < nums[0]:
                    tmp = nums[mid]
                else:
                    tmp = -float('inf')
            #二分,用tmp而不是mid与tar比较
            if tmp < target:
                lo = mid + 1
            elif tmp > target:
                hi = mid - 1
            else:
                return mid
        return -1