leetcode with python:34. Find First and Last Position of Ele

题目:

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

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

给定一排序阵列和一目标值(target),找出目标值的起始点和终点index
若目标值不在阵列内,回传[-1,-1]
时间複杂度限制为O(log n)
ex:input:[5,7,7,8,8,10],8=>output: [3,4]
explanation:第一个8index为3,最后一个8index为4

这题思路简单很多,其实这题medium还蛮像easy的,难度没那么高
其实就是做两次二分搜

class Solution:    def searchRange(self, nums: List[int], target: int) -> List[int]:        if nums==[]: #防止nums是空阵列            return [-1,-1]                l=0        r=len(nums)-1        ans=[]                while l<r:            mid=(l+r)//2            if nums[mid]==target and (mid==0 or nums[mid-1]!=target):                ans.append(mid)                break            elif nums[mid]<target:                l=mid+1            else:                r=mid-1                        if nums[l]!=target and ans==[]:            return [-1,-1]        elif nums[l]==target and ans==[]:            ans.append(l)                l=0        r=len(nums)-1                while l<r:            mid=(l+r)//2            if nums[mid]==target and (mid==len(nums)-1 or nums[mid+1]!=target):                ans.append(mid)                break            elif nums[mid]>target:                r=mid-1            else:                l=mid+1                        if len(ans)==1:            ans.append(l)                     return ans

我们要做二分搜,一次是找目标值的起始点,一次是找目标值的终点

找目标值的起始点:
用平常的二分搜下去搜寻target的位置
比较不一样的是我们就算找到target
若该位置左侧的值也是target,那这个位置并不是目标值的起始点
起始点在其左侧,所以我们让r边界往下
找到起始点后则将mid放入ans后跳出搜索

若搜索结束ans空空如也,表示未出现符合要求的mid
则我们验证l位置的值是否为target
是则将l放入ans,不是则表示target根本不在这阵列内,回传[-1,-1]

找目标值的终点:
一样用二分搜下去搜寻target的位置
且对找到的target也有特别要求
若该位置右侧的值也是target,那这个位置并不是目标值的终点
终点在其右侧,所以我们让l边界往上
找到终点后则将mid放入ans后跳出搜索

若搜索结束ans长度为1,表示未出现符合要求的mid
则将l放入ans后回传(已验证过target值存在于此阵列中)
反之直接回传ans
最后执行时间87ms(faster than 95.78%)

那我们下题见