leetcode with python:33. Search in Rotated Sorted Array

题目:

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

给定一阵列,该阵列由一升序阵列,值都是独一无二的,将其前段一部分移至后方构成
ex:[4,5,6,7,0,1,2]为[0,1,2]移到后方构成
题目给定一数(target),若target在阵列内回传其index,反之回传-1
限制时间複杂度为O(log n)

题目限制O(log n),第一时间想到二分搜
但这题是比较tricky的二分搜

class Solution:    def search(self, nums: List[int], target: int) -> int:                            if nums[-1]==target: #若target即为nums[-1],回传len(nums)-1            return len(nums)-1                if nums[0]>target and nums[-1]<target: #若target位于nums[0]和nums[-1]之间,表示target不在该阵列,回传-1            return -1                l=0        r=len(nums)-1                    if nums[-1]>target:            while l<r:                mid=(l+r)//2                if nums[mid]>target and nums[mid]<nums[-1]:                    r=mid-1                elif nums[mid]==target:                    return mid                else:                    l=mid+1                             else:            while l<r:                mid=(l+r)//2                if nums[mid]<target and nums[mid]>nums[-1]:                    l=mid+1                elif nums[mid]==target:                    return mid                else:                    r=mid-1                                                if nums[l]==target:            return l        else:            return -1

根据经验,二分搜常用于排序阵列,但这题的输入并不是
为了让我们能运用二分搜
我们可以将题目给的阵列分为两个部分,被移到后方的部分(s2)和其余的部分(s1)
以 [4,5,6,7,0,1,2]为例,[4,5,6,7]为s1,[0,1,2]为s2
也就是两个排序阵列
而我们知道s2元素小于s1的任何元素(因为它们原本是一升序排列的阵列)

我发现可以用阵列最后一数来判断target会位在s1还是s2
最后一数身为s2最大的数,第一数身为s1最小的数
若target位于nums[0]和nums[-1]之间,表示target不在该阵列,回传-1
其余若target大于nums[-1],则target会在s1
若target小于nums[-1],则target会在s2

正常分两种状况,target在s1和target在s2
设下限l=0跟上限r=len(nums)-1,mid定义为(1+r)//2

target在s2:
和一般二分搜的作法差不多,但有个特例要注意
若nums[mid]>target但nums[mid]位在s1内
照理来说nums[mid]>target我们应该要把r边界往下移
但我们已知target在s2,而此时mid在s1内
表示从l到mid这段全部都是s1的範畴,target不可能在这里
所以我们反倒要将l边界往上移去除这块区域

target在s1:
同样有个类似特例要注意
若nums[mid]< target但nums[mid]位在s2内
一般nums[mid]< target我们应该要把l边界往上移
但我们已知target在s1,而此时mid在s2内
表示从mid到r这段全部都是s2的範畴,target不可能在这里
所以我们反倒要将r边界往下移去除这块区域

二分搜到最后都没有mid回传的话
则检测l位置的值是否为target
是的话回传l,不是的话表示target不在此阵列内,回传-1
最后执行时间41ms(faster than 96.03%)

那我们下题见