題目:

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%)

那我們下題見