題目出處

34. Find First and Last Position of Element in Sorted Array

難度

easy

個人範例程式碼

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if not nums:
            return [-1, -1]

        ans = []
        ans.append(self.find_first_position(nums, target))
        ans.append(self.find_last_position(nums, target))
        return ans


    def find_first_position(self, nums, target):
        if not nums:
            return -1

        start, end = 0, len(nums)-1
        while(start + 1 < end):
            mid = (start + end) // 2
            if(nums[mid] == target): # find first, move end
                end = mid
            elif(nums[mid] < target):
                start = mid
            else: #(nums[mid] > target):
                end = mid
        else: # when quit loop
            if(nums[start] == target): # find first
                return start
            elif(nums[end] == target):
                return end
            else:
                return -1
        return -1


    def find_last_position(self, nums, target):
        if not nums:
            return -1

        start, end = 0, len(nums)-1
        while(start + 1 < end):
            mid = (start + end) // 2
            if(nums[mid] == target): # find last, move start
                start = mid
            elif(nums[mid] < target):
                start = mid
            else: #(nums[mid] > target):
                end = mid
        else: # when quit loop
            if(nums[end] == target): # find last 
                return end
            elif(nums[start] == target):
                return start
            else:
                return -1
        return -1

算法說明

此題為以下兩題的綜合題：

• 【Lintcode】python – [458] Last Position of Target 個人解法筆記
• 【Lintcode】python – [14] First Position of Target 個人解法筆記

因為重複的問題，算法又要求 log(N)，如果同時做左右搜尋會顯得程式碼比較難以閱讀與 debug，
不如就拆成兩個來寫，時間 2*O(logN) = O(logN)

拆開寫的好處我自己在撰寫時已經體驗過了，要 debug 直接找對應的哪個 function 就好!
非常的方便!!!

基本的 binary search，採用的策略為先縮小範圍再得到答案。

也就是說 left, right 縮小至最小範圍的 left, right，再去判斷答案。

• 當然比較常見的方法是：left, right 找 mid，mid 直接找到答案會更為簡潔。

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

input handling

注意 input nums 為 [] 的時候的處理，return 個 -1 給他

Boundary conditions

start 與 end 的處理一直都是 binary search 常出錯的地方，這邊要細心一些。

我採用網路上看到的 start + 1 < end 的方式，先縮小 left, right 範圍
並且不把目標放在直接找到 mid 做為答案。

再從最小範圍 left, right 中找到最終解答。

Reference

• 在排序数组中查找元素的第一个和最后一个位置 · Find First and Last Position of Element in Sorted Array